Parikshit Gopalan

I am a Researcher at Microsoft Research Silicon Valley in Mountain View, California. I work in theoretical computer science, focusing primarily on Coding theory, Computational learning, Pseudorandomness and Boolean function complexity and the interplay between them. I occasionally dabble in other areas like hardness of approximation, data-stream algorithms and computational complexity.

I am interested in applying erasure coding to storage systems for massive data. See http://research.microsoft.com/ldc for more.

My C.V.

Program Committees:

COLT'09, RANDOM'09, SODA'10, STOC'10, STOC'2012, RANDOM'2013.

Summer Interns:

Yi Wu, Raghu Meka, Raghu Meka, Yuan Zhou.

Publications

2013

Rodolfo Azevedo, John Davis, Karin Strauss, Parikshit Gopalan, Mark Manasse, and Sergey Yekhanin, Zombie Memory: Extending Memory Lifetime by Reviving Dead Blocks, in 40th International Symposium on Computer Architecture, ACM, 27 June 2013

John D. Davis, Karin Strauss, Parikshit Gopalan, Mark Manasse, and Sergey Yekhanin, Supplement to Zombie Memory: Extending Memory Lifetime by Reviving Dead Blocks, no. MSR-TR-2013-47, April 2013

2012

Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, and Salil Vadhan, Better pseudorandom generators from milder pseudorandom restrictions, in FOCS'12, IEEE, October 2012

Boaz Barak, Parikshit Gopalan, Johan Hastad, Raghu Meka, Prasad Raghavendra, and David Steurer, Making the Long Code Shorter, in FOCS'2012, IEEE, October 2012

Parikshit Gopalan, Adam Klivans, and Raghu Meka, Learning functions of halfspaces using prefix covers, in COLT'12, Journal of Machine Learning Research, June 2012

Parikshit Gopalan, Raghu Meka, and Omer Reingold, DNF Sparsification and a faster deterministic counting algorithm, in CCC'11, IEEE, June 2012

Cheng Huang, Huseyin Simitci, Yikang Xu, Aaron Ogus, Brad Calder, Parikshit Gopalan, jin Li, and Sergey Yekhanin, Erasure Coding in Windows azure storage , in USENIX ATC 2012 (Winner of the Best Paper Award), USENIX, June 2012

2011

Parikshit Gopalan, Adam Klivans, Raghu Meka, Daniel Stefankovic, Santosh Vempala, and Eric Vigoda, An FPTAS for #Knapsack and Related Counting Problems, in FOCS'11, IEEE, October 2011

Parikshit Gopalan, Cheng Huang, Huseyin Simitci, and Sergey Yekhanin, On the Locality of Codeword Symbols, in IEEE Transactions on Information theory 2012; preliminary version in Allerton 2011 (Invited paper), IEEE, September 2011

Parikshit Gopalan, Raghu Meka, Omer Reingold, and David Zuckerman, Pseudorandom Generators for Combinatorial Shapes, in STOC'11, ACM, May 2011

2010

Parikshit Gopalan, A Fourier-analytic approach to Reed-Muller decoding, in FOCS 2010, IEEE, October 2010

Zeev Dvir, Parikshit Gopalan, and Sergey Yekhanin, Matching Vector Codes, in FOCS 2010, IEEE, October 2010

Parikshit Gopalan, Adam Klivans, and Raghu Meka, Polynomial-Time Approximation Schemes for Knapsack and Related Counting Problems using Branching Programs, no. MSR-TR-2010-178, August 2010

Parikshit Gopalan and Rocco Servedio, Learning and Lower Bounds for AC0 with threshold gates, in RANDOM'10, Springer Verlag, August 2010

Parikshit Gopalan, Ryan O'Donnell, Yi Wu, and David Zuckerman, Fooling Functions of Halfspaces under Product Disributions, in CCC'10, IEEE, June 2010

2009

Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco A. Servedio, and Emanuele Viola, Bounded Independence fools halfspaces, in FOCS'09, IEEE, October 2009

Parikshit Gopalan, Ryan O'Donnell, Rocc O'Servedio, Amir Shpilka, and Karl Wimmer, Testing Fourier dimensionality and sparsity, in ICALP(1)'09, July 2009

Parikshit Gopalan, Shachar Lovett, and Amir Shpilka, On the Complexity of Boolean functions in different charactersistics, in CCC'09, July 2009

Parikshit Gopalan, Venkatesan Guruswami, and Prasad Raghavendra, List-Decoding Tensor products and Interleaved codes, in STOC'09, May 2009

Parikshit Gopalan and Jaikumar Radhakrishnan, Finding duplicates in a data stream, in SODA'09, The British Computer Society, January 2009

2008

Parikshit Gopalan, Adam Tauman Kalai, and Adam R. Klivans, A Query Algorithm for Agnostically Learning DNF?, in COLT'08 (open problem), July 2008

Parikshit Gopalan and Venkatesan Guruswami, Hardness Amplification within NP against Deterministic Algorithms, in CCC'08, June 2008

Parikshit Gopalan, Adam R. Klivans, and David Zuckerman, List-decoding Reed-Muller codes over small fields, in STOC'08, ACM, May 2008

Parikshit Gopalan, Adam Tauman Kalai, and Adam R. Klivans, Agnostically learning decision trees, in STOC'08, May 2008

2007

Parikshit Gopalan and Anna Gal, Lower Bounds on Streaming Algorithms for Approximating the Length of the Longest Increasing Subsequence, in FOCS'07, October 2007

Parikshit Gopalan, Subhash Khot, and Rishi Saket, Hardness of Reconstructing Multivariate Polynomials over Finite Fields, in FOCS'07, October 2007

Parikshit Gopalan, T. S. Jayram, Robert Krauthgamer, and Ravi Kumar, Estimating the sortedness of a data stream, in SODA'07, January 2007

2006

Vitaly Feldman, Parikshit Gopalan, Subhash Khot, and Ashok Ponnuswami, New Results for Learning Noisy Parities and Halfspaces, in FOCS'06, October 2006

Parikshit Gopalan, Computing with Polynomials over Composites, August 2006

Parikshit Gopalan, Constructing Ramsey Graphs from Boolean Function Representations, in CCC'06, July 2006

Parikshit Gopalan, Phokion Kolaitis, and Elitza Maneva, The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies, in ICALP(1), June 2006

Parikshit Gopalan, Venkatesan Guruswami, and Richard J. Lipton, Algorithms for Modular Counting of Roots of Multivariate Polynomials, in LATIN'06, March 2006

Parikshit Gopalan, Query-efficient algorithms for polynomial interpolation over composites., in SODA'06, January 2006