|
|
|
|
Pushkar Tripathi
PhD Student
Algorithms Combinatorics and Optimization(ACO)
Georgia Institute of Technology
email: pushkar dot tripathi at gatech dot edu
|
Research Experience | Publications | Links
| Resume(pdf) |
Thesis Proposal(pdf) |
My Photo Blog
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
Publications and Preprints
-
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
Work Experience
- 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
Links
Top
Site last updated:
Saturday, August 30, 2009 9:01 PM
(IST)
© Pushkar Tripathi, 2009
Site best viewed in Mozilla Firefox
@ 1024x768