Pushkar Tripathi   PhD Student Algorithms Combinatorics and Optimization(ACO) Georgia Institute of Technology email: pushkar dot tripathi at gatech dot edu

I am a second year PhD student in the ACO program at Gatech. My advisor is Vijay Vazirani.

Research Interests: Algorithms & Optimization, particularly in the area of market equilibria and mechanism design.
 

Top

Research Experience

• "Optimal Approximation Algorithms for Multi-agent Combinatorial Problems with Discounted Price Functions"    
  In this paper, we introduce and study an important subclass of submodular functions, which we call discounted price functions. These functions are succinctly representable and generalize linear cost functions. In this paper we study the following fundamental combinatorial optimization problems: Edge Cover, Spanning Tree, Perfect Matching and Shortest Path, and obtain tight upper and lower bounds for these problems. The main technical contribution of this paper is designing novel adaptive greedy algorithms for the above problems. These algorithms greedily build the solution whist rectifying mistakes made in the previous steps.
    
• "Approximability of Submodular Combinatorial Optimization Problems"    
  Applications in complex systems such as the Internet have spawned recent interest in studying situations involving multiple agents with their individual cost or utility functions. In this paper, we introduce an algorithmic framework for studying combinatorial problems in the presence of multiple agents with submodular cost functions. We study several fundamental covering problems (Vertex Cover, Shortest Path, Perfect Matching, and Spanning Tree) in this setting and establish tight upper and lower bounds for the approximability of these problems.
    
• "Visiblity of Noisy Point Cloud Data"    
  We present an improved algorithm for robustly estimating visibility from a given viewpoint for a point set, possibly corrupted with noise. Instead of performing an explicit surface reconstruction, we compute visibility based on a construction involving convex hull in an inverted space. We derive theoretical bounds for noise characteristics that can be reliably handled, and use the relations to design a robust visibility estimation algorithm. By adaptively placing viewpoints to correctly handle noise and concavity in the data, we generate locally consistent partial reconstructions. Subsequently, such local reconstructions are globally coupled using a graph theoretic framework, and the desired manifold curve or surface extracted using an approximation algorithm. We test our method on a variety of test models of varying complexity corrupted with different amounts of noise.
    
• "Almost Optimal CDMA channel Allocation"    
  We give a simple distibuted randomized algorithm for assignment of channels in CDMA protocal which achieved optimal channel utilization with high probability. The proposed method was topology unaware and only required information about the maximum degree of a node in the network.
    
• "Speeding up multi commodity flow algorithms"    
  We propose heuristic improvements in the procedure to obtain an approximation of the multicommodity flow which satisfies all demands when the cost bound is given as an input parameter. Through a series of improvements we are able to significantly reduce the number of shortest path computations. We also present a new version of the algorithm given by Garg and Konemann which is amenable to our optimizations. Finally we compare our results against those given Radzik et. al and demonstrate significant improvement in the results. We also propose methods to reduce the running time of the algorithm.
    
• "Infering Variables from Executeables"    
  We propose a scheme to statically detect memory leaks in device driver code using a provably correct technique that was guaranteed not to give false positives. The method is based on differntiating basic variables and aggregate varaibles(struct and arrays) based on their memory usage pattern.
    
• "REWIRED: Register Write Inhibition by Resource Dedication"    
  We propose REWIRED (REgisterWrite Inhibition by REsource Dedication), a technique for reducing power during high level synthesis (HLS) by selectively inhibiting the storage of function unit (FU) output data into registers. Registers are generally inferred in HLS when data produced in one clock cycle is used in a later cycle. However, when it can be established that the input registers to an FU are not changing values during a certain period, the outputs during this period can be directly read off the FU output pins without needing to store them in registers. When the life-times of such data are short, it may be possible to completely eliminate the register storage operation, thereby reducing power. We present a genetic algorithmformulation and a heuristic for maximizing the number of register stores that can be inhibited in a scheduled data flow graph (DFG) during behavioral synthesis.
    

Top

•   Gagan Goel, Chinmay Karande, Pushkar Tripathi and Lei Wang. “Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions”. In IEEE Symposium on Foundations of Computer Science (FOCS) 2009, Atlanta, USA. [pdf]
      
•   Pushkar Tripathi, Rohan Jain, Srikanth Kurra and P.R. Panda. “REWIRED: Register Write Inhibition by Resource Dedication”, In Asia Pacific Design Automation Conference (ASPDAC) 2008, Seoul, Korea. [pdf]
      
•   Ravish Mehra, Pushkar Tripathi and Niloy Mitra. “Visibility of Noisy Point Cloud Data”. Submitted Eurographics 2010, Norkoping, Sweden. [pdf]
      
•   Gagan Goel, Pushkar Tripathi and Lei Wang. “Optimal Approximation Algorithms for Multi-agent Combinatorial Problems with Discounted Price Functions”. Submitted 2009. [pdf]
      
•   Naveen Garg, Shubham Mittal and Pushkar Tripathi. “Computing minimum cost multicommodity flows for large graphs”. Submitted 2009. [pdf]
      
•   G. Ramalingam, Pushkar Tripathi and L. Valega. “Inferring Top-Level Variables from Executables”. Technical Report, Microsoft Research India, Dec 2007. [pdf]
      
•   Pushkar Tripathi, Pushkar Sachdeva and Mustafa Amar. “Alomost Optimal CDMA Channel Allocation”. Manuscript 2009. [pdf]
      

Top

•   Worked as a summer intern at Google, Pittsburgh, USA from May 2009 to August 2009.
      
•   Worked as a summer intern at Microsoft Research, India, Bangalore from May 2007 to August 2007.
      

Top

Conferences

• 20th International Conference on VLSI Design, Bangalore, 2007 [link]    
• 6th International Conference on Embedded Systems, Bangalore, 2007.[link]    
• 13th Asia Pacific Design Automation Conference, Seoul, 2008.[link]  
• 50th Annual IEEE Symposium on Foundations of Computer Science, Atlanta, 2009 [link]    

Top

•    My puzzle contests  -Contains papers and software that I developed for various puzzle and algorithms competitions
•    My Photo-Blog
•    Darjeeling trip Pics
•    Arunachal Trip Pics

Top

Site last updated: Saturday, August 30, 2009 9:01 PM (IST)

© Pushkar Tripathi, 2009
Site best viewed in Mozilla Firefox @ 1024x768