Parikshit Gopalan

Parikshit Gopalan, Raghu Meka, Omer Reingold: DNF sparsification and a faster deterministic counting algorithm. Computational Complexity 22(2): 275-310 (2013)

Parikshit Gopalan, Adam R. Klivans, Raghu Meka: Learning Functions of Halfspaces using Prefix Covers. Journal of Machine Learning Research - Proceedings Track 23: 15.1-15.10 (2012)

Parikshit Gopalan, Cheng Huang, Huseyin Simitci, Sergey Yekhanin: On the Locality of Codeword Symbols. IEEE Transactions on Information Theory 58(11): 6925-6934 (2012)

Parikshit Gopalan, Raghu Meka, Omer Reingold: DNF Sparsification and a Faster Deterministic Counting Algorithm. IEEE Conference on Computational Complexity 2012: 126-135

Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil P. Vadhan: Better Pseudorandom Generators from Milder Pseudorandom Restrictions. FOCS 2012: 120-129

Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer: Making the Long Code Shorter. FOCS 2012: 370-379

Parikshit Gopalan, Raghu Meka, Omer Reingold: DNF Sparsification and a Faster Deterministic Counting Algorithm. CoRR abs/1205.3534 (2012)

Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil P. Vadhan: Better Pseudorandom Generators from Milder Pseudorandom Restrictions. CoRR abs/1210.0049 (2012)

Parikshit Gopalan, Raghu Meka, Omer Reingold: DNF Sparsification and a Faster Deterministic Counting. Electronic Colloquium on Computational Complexity (ECCC) 19: 60 (2012)

Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil P. Vadhan: Better pseudorandom generators from milder pseudorandom restrictions. Electronic Colloquium on Computational Complexity (ECCC) 19: 123 (2012)

Parikshit Gopalan, Venkatesan Guruswami: Hardness amplification within NP against deterministic algorithms. J. Comput. Syst. Sci. 77(1): 107-121 (2011)

Parikshit Gopalan, Ryan O'Donnell, Rocco A. Servedio, Amir Shpilka, Karl Wimmer: Testing Fourier Dimensionality and Sparsity. SIAM J. Comput. 40(4): 1075-1100 (2011)

Zeev Dvir, Parikshit Gopalan, Sergey Yekhanin: Matching Vector Codes. SIAM J. Comput. 40(4): 1154-1178 (2011)

Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra: List Decoding Tensor Products and Interleaved Codes. SIAM J. Comput. 40(5): 1432-1462 (2011)

Parikshit Gopalan, Adam Klivans, Raghu Meka, Daniel Stefankovic, Santosh Vempala, Eric Vigoda: An FPTAS for #Knapsack and Related Counting Problems. FOCS 2011: 817-826

Parikshit Gopalan, Raghu Meka, Omer Reingold, David Zuckerman: Pseudorandom generators for combinatorial shapes. STOC 2011: 253-262

Parikshit Gopalan, Cheng Huang, Huseyin Simitci, Sergey Yekhanin: On the Locality of Codeword Symbols. CoRR abs/1106.3625 (2011)

Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer: Making the long code shorter, with applications to the Unique Games Conjecture. CoRR abs/1111.0405 (2011)

Parikshit Gopalan, Cheng Huang, Huseyin Simitci, Sergey Yekhanin: On the Locality of Codeword Symbols. Electronic Colloquium on Computational Complexity (ECCC) 18: 100 (2011)

Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer: Making the long code shorter, with applications to the Unique Games Conjecture. Electronic Colloquium on Computational Complexity (ECCC) 18: 142 (2011)

Parikshit Gopalan, Amir Shpilka, Shachar Lovett: The Complexity of Boolean Functions in Different Characteristics. Computational Complexity 19(2): 235-263 (2010)

Parikshit Gopalan, Subhash Khot, Rishi Saket: Hardness of Reconstructing Multivariate Polynomials over Finite Fields. SIAM J. Comput. 39(6): 2598-2621 (2010)

Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco A. Servedio, Emanuele Viola: Bounded Independence Fools Halfspaces. SIAM J. Comput. 39(8): 3441-3462 (2010)

Anna Gál, Parikshit Gopalan: Lower Bounds on Streaming Algorithms for Approximating the Length of the Longest Increasing Subsequence. SIAM J. Comput. 39(8): 3463-3479 (2010)

Parikshit Gopalan, Rocco A. Servedio: Learning and Lower Bounds for AC⁰ with Threshold Gates. APPROX-RANDOM 2010: 588-601

Parikshit Gopalan, Ryan O'Donnell, Yi Wu, David Zuckerman: Fooling Functions of Halfspaces under Product Distributions. IEEE Conference on Computational Complexity 2010: 223-234

Parikshit Gopalan: A Fourier-Analytic Approach to Reed-Muller Decoding. FOCS 2010: 685-694

Zeev Dvir, Parikshit Gopalan, Sergey Yekhanin: Matching Vector Codes. FOCS 2010: 705-714

Parikshit Gopalan, Ryan O'Donnell, Yi Wu, David Zuckerman: Fooling functions of halfspaces under product distributions. CoRR abs/1001.1593 (2010)

Parikshit Gopalan, Adam Klivans, Raghu Meka: Polynomial-Time Approximation Schemes for Knapsack and Related Counting Problems using Branching Programs. CoRR abs/1008.3187 (2010)

Yi Wu, Ryan O'Donnell, David Zuckerman, Parikshit Gopalan: Fooling functions of halfspaces under product distributions. Electronic Colloquium on Computational Complexity (ECCC) 17: 6 (2010)

Zeev Dvir, Parikshit Gopalan, Sergey Yekhanin: Matching Vector Codes. Electronic Colloquium on Computational Complexity (ECCC) 17: 12 (2010)

Parikshit Gopalan, Rocco A. Servedio: Learning and Lower Bounds for AC⁰ with Threshold Gates. Electronic Colloquium on Computational Complexity (ECCC) 17: 74 (2010)

Parikshit Gopalan, Adam Klivans, Raghu Meka: Polynomial-Time Approximation Schemes for Knapsack and Related Counting Problems using Branching Programs. Electronic Colloquium on Computational Complexity (ECCC) 17: 133 (2010)

Parikshit Gopalan, Raghu Meka, Omer Reingold, David Zuckerman: Pseudorandom Generators for Combinatorial Shapes. Electronic Colloquium on Computational Complexity (ECCC) 17: 176 (2010)

Parikshit Gopalan, Phokion G. Kolaitis, Elitza N. Maneva, Christos H. Papadimitriou: The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies. SIAM J. Comput. 38(6): 2330-2355 (2009)

Vitaly Feldman, Parikshit Gopalan, Subhash Khot, Ashok Kumar Ponnuswami: On Agnostic Learning of Parities, Monomials, and Halfspaces. SIAM J. Comput. 39(2): 606-645 (2009)

Parikshit Gopalan, Shachar Lovett, Amir Shpilka: On the Complexity of Boolean Functions in Different Characteristics. IEEE Conference on Computational Complexity 2009: 173-183

Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco A. Servedio, Emanuele Viola: Bounded Independence Fools Halfspaces. FOCS 2009: 171-180

Parikshit Gopalan, Ryan O'Donnell, Rocco A. Servedio, Amir Shpilka, Karl Wimmer: Testing Fourier Dimensionality and Sparsity. ICALP (1) 2009: 500-512

Parikshit Gopalan, Jaikumar Radhakrishnan: Finding duplicates in a data stream. SODA 2009: 402-411

Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra: List decoding tensor products and interleaved codes. STOC 2009: 13-22

Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco A. Servedio, Emanuele Viola: Bounded Independence Fools Halfspaces. CoRR abs/0902.3757 (2009)

Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco A. Servedio, Emanuele Viola: Bounded Independence Fools Halfspaces. Electronic Colloquium on Computational Complexity (ECCC) 16: 16 (2009)

Parikshit Gopalan: A Fourier-analytic approach to Reed-Muller decoding. Electronic Colloquium on Computational Complexity (ECCC) 16: 37 (2009)

Parikshit Gopalan, Shachar Lovett, Amir Shpilka: On the Complexity of Boolean Functions in Different Characteristics. Electronic Colloquium on Computational Complexity (ECCC) 16: 48 (2009)

Parikshit Gopalan: A note on Efremenko's Locally Decodable Codes. Electronic Colloquium on Computational Complexity (ECCC) 16: 69 (2009)

Parikshit Gopalan, Venkatesan Guruswami, Richard J. Lipton: Algorithms for Modular Counting of Roots of Multivariate Polynomials. Algorithmica 50(4): 479-496 (2008)

Saugata Basu, Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton: Polynomials that Sign Represent Parity and Descartes' Rule of Signs. Computational Complexity 17(3): 377-406 (2008)

Parikshit Gopalan: Query-Efficient Algorithms for Polynomial Interpolation over Composites. SIAM J. Comput. 38(3): 1033-1057 (2008)

Parikshit Gopalan, Venkatesan Guruswami: Hardness Amplification within NP against Deterministic Algorithms. IEEE Conference on Computational Complexity 2008: 19-30

Parikshit Gopalan, Adam Kalai, Adam R. Klivans: A Query Algorithm for Agnostically Learning DNF?. COLT 2008: 515-516

Parikshit Gopalan, Adam R. Klivans, David Zuckerman: List-decoding reed-muller codes over small fields. STOC 2008: 265-274

Parikshit Gopalan, Adam Tauman Kalai, Adam R. Klivans: Agnostically learning decision trees. STOC 2008: 527-536

Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra: List Decoding Tensor Products and Interleaved Codes. CoRR abs/0811.4395 (2008)

Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra: List Decoding Tensor Products and Interleaved Codes. Electronic Colloquium on Computational Complexity (ECCC) 15(105) (2008)

Anna Gál, Parikshit Gopalan: Lower Bounds on Streaming Algorithms for Approximating the Length of the Longest Increasing Subsequence. FOCS 2007: 294-304

Parikshit Gopalan, Subhash Khot, Rishi Saket: Hardness of Reconstructing Multivariate Polynomials over Finite Fields. FOCS 2007: 349-359

Parikshit Gopalan, T. S. Jayram, Robert Krauthgamer, Ravi Kumar: Estimating the sortedness of a data stream. SODA 2007: 318-327

Parikshit Gopalan, Subhash Khot, Rishi Saket: Hardness of Reconstructing Multivariate Polynomials over Finite Fields. Electronic Colloquium on Computational Complexity (ECCC) 14(073) (2007)

Parikshit Gopalan, Venkatesan Guruswami: Deterministic Hardness Amplification via Local GMD Decoding. Electronic Colloquium on Computational Complexity (ECCC) 14(089) (2007)

Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton: Symmetric polynomials over Z_m and simultaneous communication protocols. J. Comput. Syst. Sci. 72(2): 252-285 (2006)

Parikshit Gopalan: Constructing Ramsey Graphs from Boolean Function Representations. IEEE Conference on Computational Complexity 2006: 115-128

Vitaly Feldman, Parikshit Gopalan, Subhash Khot, Ashok Kumar Ponnuswami: New Results for Learning Noisy Parities and Halfspaces. FOCS 2006: 563-574

Parikshit Gopalan, Phokion G. Kolaitis, Elitza N. Maneva, Christos H. Papadimitriou: The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies. ICALP (1) 2006: 346-357

Parikshit Gopalan, Venkatesan Guruswami, Richard J. Lipton: Algorithms for Modular Counting of Roots of Multivariate Polynomials. LATIN 2006: 544-555

Parikshit Gopalan: Query-efficient algorithms for polynomial interpolation over composites. SODA 2006: 908-917

Parikshit Gopalan, Phokion G. Kolaitis, Elitza N. Maneva, Christos H. Papadimitriou: The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies. CoRR abs/cs/0609072 (2006)

Vitaly Feldman, Parikshit Gopalan, Subhash Khot, Ashok Kumar Ponnuswami: New Results for Learning Noisy Parities and Halfspaces. Electronic Colloquium on Computational Complexity (ECCC) 13(059) (2006)

Parikshit Gopalan, Phokion G. Kolaitis, Elitza N. Maneva, Christos H. Papadimitriou: The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies. Electronic Colloquium on Computational Complexity (ECCC) 13(094) (2006)

Parikshit Gopalan, Howard J. Karloff, Aranyak Mehta, Milena Mihail, Nisheeth K. Vishnoi: Caching with Expiration Times for Internet Applications. Internet Mathematics 2(2): 165-184 (2005)

Parikshit Gopalan: Constructing Ramsey Graphs from Boolean Function Representations. Electronic Colloquium on Computational Complexity (ECCC)(143) (2005)

Saugata Basu, Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton: Polynomials That Sign Represent Parity and Descartes Rule of Signs. IEEE Conference on Computational Complexity 2004: 223-235

Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton: The Degree of Threshold Mod 6 and Diophantine Equations. Electronic Colloquium on Computational Complexity (ECCC)(022) (2004)

Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton: Symmetric Polynomials over Z_m and Simultaneous Communication Protocol. FOCS 2003: 450-459

Parikshit Gopalan, Richard J. Lipton, Aranyak Mehta: Randomized Time-Space Tradeoffs for Directed Graph Connectivity. FSTTCS 2003: 208-216

Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton: Symmetric Polynomials over Z_m and Simultaneous Communication Protocols. Electronic Colloquium on Computational Complexity (ECCC)(047) (2003)

Parikshit Gopalan, Howard J. Karloff, Aranyak Mehta, Milena Mihail, Nisheeth K. Vishnoi: Caching with expiration times. SODA 2002: 540-547