I am a Researcher at Microsoft based in Mountain View, California. I work with the Azure Storage team.
I am interested in theoretical computer science, focusing on Coding theory, Boolean function analysis, Pseudorandomness and Computational Complexity and the interplay between them. I work on several algorithmic problems (decoding, testing, learning, derandomization) under the guise of complexity theory.
On the applied side, I have been working on fault-tolerant storage and erasure coding for cloud storage. My collaborators and I introduced the notion of local repair for erasure coded data. Our work has been deployed in several Microsoft products and has won internal and external awards including
- the 2014 IEEE Communication and Information Theory Society Joint Paper Prize.
- the 2013 Microsoft Technical Community Network Storage Technical Award.
- the 2012 USENIX ATC Best Paper Award.
Parikshit Gopalan, Cheng Huang, Bob Jenkins, and Sergey Yekhanin, Explicit Maximally Recoverable Codes with Locality, in IEEE Transactions on Information Theory, IEEE – Institute of Electrical and Electronics Engineers, June 2014.
Parikshit Gopalan and Amir Yehudayoff, Inequalities and tail bounds for elementary symmetric polynomials, no. MSR-TR-2014-131, March 2014.
Parikshit Gopalan, Salil Vadhan, and Yuan Zhou, Locally Testable Codes and Cayley Graphs, in Innovations in Theoretical Computer Science (ITCS'2014), ACM – Association for Computing Machinery, January 2014.
Rodolfo Azevedo, John Davis, Karin Strauss, Parikshit Gopalan, Mark Manasse, and Sergey Yekhanin, Zombie Memory: Extending Memory Lifetime by Reviving Dead Blocks, in ISCA 2013 (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.
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); winner of the 2014 IEEE Communication and Information Theory Society Joint Paper Prize, IEEE, November 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, Raghu Meka, Omer Reingold, Luca Trevisan, and Salil Vadhan, Better pseudorandom generators from milder pseudorandom restrictions, in FOCS'12, IEEE, October 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.
Parikshit Gopalan, Raghu Meka, and Omer Reingold, DNF Sparsification and a faster deterministic counting algorithm, in CCC'11, IEEE, June 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, 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, Raghu Meka, Omer Reingold, and David Zuckerman, Pseudorandom Generators for Combinatorial Shapes, in STOC'11, ACM, May 2011.
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 and Rocco Servedio, Learning and Lower Bounds for AC0 with threshold gates, in RANDOM'10, Springer Verlag, August 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, Ryan O'Donnell, Yi Wu, and David Zuckerman, Fooling Functions of Halfspaces under Product Disributions, in CCC'10, IEEE, June 2010.
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.
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 Tauman Kalai, and Adam R. Klivans, Agnostically learning decision trees, in STOC'08, May 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, Subhash Khot, and Rishi Saket, Hardness of Reconstructing Multivariate Polynomials over Finite Fields, in FOCS'07, October 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, T. S. Jayram, Robert Krauthgamer, and Ravi Kumar, Estimating the sortedness of a data stream, in SODA'07, January 2007.
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.