Parikshit Gopalan

Parikshit Gopalan

I will be joining MSR Silicon Valley in Fall 2008.
I was until recently a postdoc at the University of Washington hosted by Venkatesan Guruswami.
Prior to this, I had a short but enjoyable stint as a postdoc at UT Austin hosted by Adam Klivans.
I received my Ph.D from the theory group, ACO program at Georgia Tech. My advisor was Dick Lipton.
I received a bachelor's degree from the CSE department, IIT Bombay.
I grew up in India, in the city formerly known as Bombay.


Research Interests : Theoretical Computer Science, especially areas and problems with an algebraic flavor. My research focuses on four main areas: I am also interested in other areas such as Data-stream algorithms, Computational algebra and Communication complexity.

CV : (pdf)   (ps)
Research Statement : (pdf)   (ps)
Contact : I am currently in Israel, visiting the Technion. The quickest way to reach me is by email: parik dot g at gmail dot com

Publications :

Finding duplicates in a data stream.
with Jaikumar Radhakrishnan.
Submitted.

Testing Fourier dimensionality and sparsity.
with Ryan O'Donnell, Rocco Servedio, Amir Shpilka and Karl Wimmer.
Submitted.

A Query Algorithm for Agnostically Learning DNFs? (a 2-page open problem)
with Adam Tauman Kalai and Adam R. Klivans.
COLT'08.
(ps)  (pdf)  

Hardness Amplification within NP against Deterministic Algorithms.
with Venkatesan Guruswami.
CCC'08.
(abstract)   Conf: (ps)  (pdf)   Older Version: (ps)  (pdf)  

Agnostically Learning Decision Trees.
with Adam Tauman Kalai and Adam R. Klivans.
STOC'08.
(abstract)   (ps)  (pdf)  

List-Decoding Reed Muller codes over small fields.
with Adam R. Klivans and David Zuckerman.
STOC'08.
(abstract)   (ps)  (pdf)  

Lower Bounds on Streaming Algorithms for Approximating the Length of the Longest Increasing Subsequence.
with Anna Gal.
FOCS'07.
(abstract) Conf: (ps)  (pdf)  

Hardness of Reconstructing Multivariate Polynomials over Finite Fields.
with Subhash Khot and Rishi Saket.
FOCS'07 (invited to SICOMP special issue for FOCS'07).
(abstract) Conf: (ps)  (pdf)   Full: (ps)  (pdf)  

Estimating the Sortedness of a Data Stream.
with T. S. Jayram, Robert Krauthgamer and Ravi Kumar.
SODA'07.
(abstract) Conf: (ps)  (pdf)  

Computing with Polynomials over Composites.
Ph.D Thesis.
(abstract) (ps)  (pdf)  

New Results for Learning Noisy Parities and Halfspaces.
with Vitaly Feldman, Subhash Khot and Ashok K. Ponnuswami.
FOCS'06.     (Invited to SICOMP special issue for FOCS'06)
(abstract) Conf: (ps)  (pdf)   Full: (ps)  (pdf)  

The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies.
with Phokion G. Kolaitis, Elitza N. Maneva and Christos H. Papadimitriou.
ICALP'06.
(abstract) Conf: (ps)  (pdf)   Full: (ps)  (pdf)  

Constructing Ramsey Graphs from Boolean Function Representations.
CCC'06.
(abstract)  Conf: (ps)  (pdf)   Full: (ps)  (pdf)  

Algorithms for Modular Counting of Roots of Multivariate Polynomials.
with Venkatesan Guruswami and Richard J. Lipton.
LATIN'06.     (Invited to Algorithmica special issue for LATIN'06)
(abstract)  Full: (ps)  (pdf)

Query-Efficient Algorithms for Polynomial Interpolation over Composites.
SODA'06.    (Accepted to SICOMP)
(abstract)  Conf: (ps)  (pdf)   Full: (ps)  (pdf)  

Polynomials that Sign Represent Parity and Descartes Rule of Signs.
with Saugata Basu, Nayantara Bhatnagar, Richard J. Lipton.
CCC'04.     (Accepted to Computational Complexity)
(abstract)  Conf: (ps)  (pdf)  

The combined JCSS version of the two papers below: (ps)   (pdf)  

The Degree of Threshold mod 6 and Diophantine Equations.
with Nayantara Bhatnagar, Richard J. Lipton.
ECCC TR04-022.
(abstract)  (ps)   (pdf)  

Symmetric Polynomials over Zm and Simultaneous Communication Protocols.
with Nayantara Bhatnagar, Richard J. Lipton.
FOCS'03.     (Full version in JCSS special issue for FOCS'03)
(abstract)  Conf: (ps)  (pdf)  

Randomized Time Space Tradeoffs for Directed Graph Connectivity.
with Richard J. Lipton, Aranyak Mehta.
FSTTCS'03.
(abstract)  (ps)   (pdf)

Caching with Expiration Times.
with Howard Karloff, Aranyak Mehta, Milena Mihail, Nisheeth Vishnoi.
SODA'02; Appears in Internet Mathematics.
(abstract)  Full: (ps)   (pdf)