Parikshit Gopalan

According to our database, Parikshit Gopalan authored at least 84 papers between 2002 and 2025.

Collaborative distances:

• Dijkstra number of two.
• Erdős number of three.

2025

Calibration through the Lens of Indistinguishability.

Parikshit Gopalan, Lunjia Hu

CoRR, September, 2025

How Global Calibration Strengthens Multiaccuracy.

Sílvia Casacuberta, Parikshit Gopalan, Varun Kanade, Omer Reingold

CoRR, April, 2025

Provable Uncertainty Decomposition via Higher-Order Calibration.

Gustaf Ahdritz, Aravind Gollakota, Parikshit Gopalan, Charlotte Peale, Udi Wieder

Proceedings of the Thirteenth International Conference on Learning Representations, 2025

When Does a Predictor Know Its Own Loss?

Aravind Gollakota, Parikshit Gopalan, Aayush Karan, Charlotte Peale, Udi Wieder

Proceedings of the 6th Symposium on Foundations of Responsible Computing, 2025

2024

Learning to Route with Confidence Tokens.

Yu-Neng Chuang, Helen Zhou, Prathusha Kameswara Sarma, Parikshit Gopalan, John Boccio, Sara Bolouki, Xia Hu

CoRR, 2024

Omnipredictors for Regression and the Approximate Rank of Convex Functions.

Parikshit Gopalan, Princewill Okoroafor, Prasad Raghavendra, Abhishek Shetty, Mihir Singhal

CoRR, 2024

Loss Minimization Yields Multicalibration for Large Neural Networks.

Jaroslaw Blasiok, Parikshit Gopalan, Lunjia Hu, Adam Tauman Kalai, Preetum Nakkiran

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

Omnipredictors for regression and the approximate rank of convex functions.

Parikshit Gopalan, Princewill Okoroafor, Prasad Raghavendra, Abhishek Sherry, Mihir Singhal

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

On Computationally Efficient Multi-Class Calibration.

Parikshit Gopalan, Lunjia Hu, Guy N. Rothblum

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

2023

Characterizing notions of omniprediction via multicalibration.

Parikshit Gopalan, Michael P. Kim, Omer Reingold

CoRR, 2023

A Unifying Theory of Distance from Calibration.

Jaroslaw Blasiok, Parikshit Gopalan, Lunjia Hu, Preetum Nakkiran

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Swap Agnostic Learning, or Characterizing Omniprediction via Multicalibration.

Parikshit Gopalan, Michael P. Kim, Omer Reingold

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Agnostically Learning Single-Index Models using Omnipredictors.

Aravind Gollakota, Parikshit Gopalan, Adam R. Klivans, Konstantinos Stavropoulos

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

When Does Optimizing a Proper Loss Yield Calibration?

Jaroslaw Blasiok, Parikshit Gopalan, Lunjia Hu, Preetum Nakkiran

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Loss Minimization Through the Lens Of Outcome Indistinguishability.

Parikshit Gopalan, Lunjia Hu, Michael P. Kim, Omer Reingold, Udi Wieder

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

2022

Overlook: Differentially Private Exploratory Visualization for Big Data.

Mihai Budiu, Pratiksha Thaker, Parikshit Gopalan, Udi Wieder, Matei Zaharia

J. Priv. Confidentiality, 2022

KL Divergence Estimation with Multi-group Attribution.

Parikshit Gopalan, Nina Narodytska, Omer Reingold, Vatsal Sharan, Udi Wieder

CoRR, 2022

Omnipredictors.

Parikshit Gopalan, Adam Tauman Kalai, Omer Reingold, Vatsal Sharan, Udi Wieder

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Low-Degree Multicalibration.

Parikshit Gopalan, Michael P. Kim, Mihir Singhal, Shengjia Zhao

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

Multicalibrated Partitions for Importance Weights.

Parikshit Gopalan, Omer Reingold, Vatsal Sharan, Udi Wieder

Proceedings of the International Conference on Algorithmic Learning Theory, 29 March, 2022

2020

Concentration for Limited Independence via Inequalities for the Elementary Symmetric Polynomials.

Parikshit Gopalan, Amir Yehudayoff

Theory Comput., 2020

Finding Skewed Subcubes Under a Distribution.

Parikshit Gopalan, Roie Levin, Udi Wieder

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

2019

Hillview: A trillion-cell spreadsheet for big data.

Mihai Budiu, Parikshit Gopalan, Lalith Suresh, Udi Wieder, Han Kruiger, Marcos K. Aguilera

Proc. VLDB Endow., 2019

PIDForest: Anomaly Detection via Partial Identification.

Parikshit Gopalan, Vatsal Sharan, Udi Wieder

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

2018

Faster Anomaly Detection via Matrix Sketching.

Parikshit Gopalan, Vatsal Sharan, Udi Wieder

CoRR, 2018

Stable and Consistent Membership at Scale with Rapid.

Lalith Suresh, Dahlia Malkhi, Parikshit Gopalan, Ivan Porto Carreiro, Zeeshan Lokhandwala

Proceedings of the 2018 USENIX Annual Technical Conference, 2018

Efficient Anomaly Detection via Matrix Sketching.

Vatsal Sharan, Parikshit Gopalan, Udi Wieder

Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

2017

Maximally Recoverable Codes for Grid-like Topologies.

Parikshit Gopalan, Guangda Hu, Swastik Kopparty, Shubhangi Saraf, Carol Wang, Sergey Yekhanin

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

2016

Degree and Sensitivity: tails of two distributions.

Parikshit Gopalan, Rocco A. Servedio, Avishay Tal, Avi Wigderson

Electron. Colloquium Comput. Complex., 2016

Maximally Recoverable Codes for Grid-like Topologies.

Parikshit Gopalan, Guangda Hu, Shubhangi Saraf, Carol Wang, Sergey Yekhanin

CoRR, 2016

Smooth Boolean Functions are Easy: Efficient Algorithms for Low-Sensitivity Functions.

Parikshit Gopalan, Noam Nisan, Rocco A. Servedio, Kunal Talwar, Avi Wigderson

Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016

Degree and Sensitivity: Tails of Two Distributions.

Parikshit Gopalan, Rocco A. Servedio, Avi Wigderson

Proceedings of the 31st Conference on Computational Complexity, 2016

2015

Public Projects, Boolean Functions, and the Borders of Border's Theorem.

Parikshit Gopalan, Noam Nisan, Tim Roughgarden

Proceedings of the Sixteenth ACM Conference on Economics and Computation, 2015

Pseudorandomness via the Discrete Fourier Transform.

Parikshit Gopalan, Daniel M. Kane, Raghu Meka

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014

Inequalities and tail bounds for elementary symmetric polynomials.

Parikshit Gopalan, Amir Yehudayoff

Electron. Colloquium Comput. Complex., 2014

Inequalities and tail bounds for elementary symmetric polynomial.

Parikshit Gopalan, Amir Yehudayoff

CoRR, 2014

Pseudorandomness for concentration bounds and signed majorities.

Parikshit Gopalan, Daniel M. Kane, Raghu Meka

CoRR, 2014

Locally testable codes and cayley graphs.

Parikshit Gopalan, Salil P. Vadhan, Yuan Zhou

Proceedings of the Innovations in Theoretical Computer Science, 2014

2013

Explicit Maximally Recoverable Codes with Locality.

Parikshit Gopalan, Cheng Huang, Bob Jenkins, Sergey Yekhanin

Electron. Colloquium Comput. Complex., 2013

Zombie memory: extending memory lifetime by reviving dead blocks.

Rodolfo Azevedo, John D. Davis, Karin Strauss, Parikshit Gopalan, Mark S. Manasse, Sergey Yekhanin

Proceedings of the 40th Annual International Symposium on Computer Architecture, 2013

2012

Learning Functions of Halfspaces using Prefix Covers.

Parikshit Gopalan, Adam R. Klivans, Raghu Meka

Proceedings of the COLT 2012, 2012

DNF Sparsification and a Faster Deterministic Counting.

Parikshit Gopalan, Raghu Meka, Omer Reingold

Electron. Colloquium Comput. Complex., 2012

Erasure Coding in Windows Azure Storage.

Cheng Huang, Huseyin Simitci, Yikang Xu, Aaron Ogus, Brad Calder, Parikshit Gopalan, Jin Li, Sergey Yekhanin

Proceedings of the 2012 USENIX Annual Technical Conference, 2012

Better Pseudorandom Generators from Milder Pseudorandom Restrictions.

Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil P. Vadhan

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

Making the Long Code Shorter.

Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

DNF Sparsification and a Faster Deterministic Counting Algorithm.

Parikshit Gopalan, Raghu Meka, Omer Reingold

Proceedings of the 27th Conference on Computational Complexity, 2012

2011

On the Locality of Codeword Symbols.

Parikshit Gopalan, Cheng Huang, Huseyin Simitci, Sergey Yekhanin

Electron. Colloquium Comput. Complex., 2011

Making the long code shorter, with applications to the Unique Games Conjecture.

Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer

Electron. Colloquium Comput. Complex., 2011

Pseudorandom generators for combinatorial shapes.

Parikshit Gopalan, Raghu Meka, Omer Reingold, David Zuckerman

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

An FPTAS for #Knapsack and Related Counting Problems.

Parikshit Gopalan, Adam R. Klivans, Raghu Meka, Daniel Stefankovic, Santosh S. Vempala, Eric Vigoda

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

2010

Polynomial-Time Approximation Schemes for Knapsack and Related Counting Problems using Branching Programs.

Parikshit Gopalan, Adam R. Klivans, Raghu Meka

Electron. Colloquium Comput. Complex., 2010

A Fourier-Analytic Approach to Reed-Muller Decoding.

Parikshit Gopalan

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

Matching Vector Codes.

Zeev Dvir, Parikshit Gopalan, Sergey Yekhanin

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

Fooling Functions of Halfspaces under Product Distributions.

Parikshit Gopalan, Ryan O'Donnell, Yi Wu, David Zuckerman

Proceedings of the 25th Annual IEEE Conference on Computational Complexity, 2010

Learning and Lower Bounds for AC⁰ with Threshold Gates.

Parikshit Gopalan, Rocco A. Servedio

Proceedings of the Approximation, 2010

2009

On Agnostic Learning of Parities, Monomials, and Halfspaces.

Vitaly Feldman, Parikshit Gopalan, Subhash Khot, Ashok Kumar Ponnuswami

SIAM J. Comput., 2009

A note on Efremenko's Locally Decodable Codes.

Parikshit Gopalan

Electron. Colloquium Comput. Complex., 2009

List decoding tensor products and interleaved codes.

Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Finding duplicates in a data stream.

Parikshit Gopalan, Jaikumar Radhakrishnan

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Testing Fourier Dimensionality and Sparsity.

Parikshit Gopalan, Ryan O'Donnell, Rocco A. Servedio, Amir Shpilka, Karl Wimmer

Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

Bounded Independence Fools Halfspaces.

Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco A. Servedio, Emanuele Viola

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

On the Complexity of Boolean Functions in Different Characteristics.

Parikshit Gopalan, Shachar Lovett, Amir Shpilka

Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

2008

List-decoding reed-muller codes over small fields.

Parikshit Gopalan, Adam R. Klivans, David Zuckerman

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Agnostically learning decision trees.

Parikshit Gopalan, Adam Tauman Kalai, Adam R. Klivans

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

A Query Algorithm for Agnostically Learning DNF?.

Parikshit Gopalan, Adam Kalai, Adam R. Klivans

Proceedings of the 21st Annual Conference on Learning Theory, 2008

Hardness Amplification within NP against Deterministic Algorithms.

Parikshit Gopalan, Venkatesan Guruswami

Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 2008

2007

Deterministic Hardness Amplification via Local GMD Decoding.

Parikshit Gopalan, Venkatesan Guruswami

Electron. Colloquium Comput. Complex., 2007

Estimating the sortedness of a data stream.

Parikshit Gopalan, T. S. Jayram, Robert Krauthgamer, Ravi Kumar

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Hardness of Reconstructing Multivariate Polynomials over Finite Fields.

Parikshit Gopalan, Subhash Khot, Rishi Saket

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, 2007

Lower Bounds on Streaming Algorithms for Approximating the Length of the Longest Increasing Subsequence.

Anna Gál, Parikshit Gopalan

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, 2007

2006

Computing with Polynomials over Composites.

Parikshit Gopalan

PhD thesis, 2006

Symmetric polynomials over Z_<i>m</i> and simultaneous communication protocols.

Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton

J. Comput. Syst. Sci., 2006

Query-efficient algorithms for polynomial interpolation over composites.

Parikshit Gopalan

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Algorithms for Modular Counting of Roots of Multivariate Polynomials.

Parikshit Gopalan, Venkatesan Guruswami, Richard J. Lipton

Proceedings of the LATIN 2006: Theoretical Informatics, 2006

The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies.

Parikshit Gopalan, Phokion G. Kolaitis, Elitza N. Maneva, Christos H. Papadimitriou

Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

New Results for Learning Noisy Parities and Halfspaces.

Vitaly Feldman, Parikshit Gopalan, Subhash Khot, Ashok Kumar Ponnuswami

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 2006

Constructing Ramsey Graphs from Boolean Function Representations.

Parikshit Gopalan

Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 2006

2005

Caching with Expiration Times for Internet Applications.

Parikshit Gopalan, Howard J. Karloff, Aranyak Mehta, Milena Mihail, Nisheeth K. Vishnoi

Internet Math., 2005

2004

The Degree of Threshold Mod 6 and Diophantine Equations

Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton

Electron. Colloquium Comput. Complex., 2004

Polynomials That Sign Represent Parity and Descartes Rule of Signs.

Saugata Basu, Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton

Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004

2003

Symmetric Polynomials over Z_m and Simultaneous Communication Protocols

Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton

Electron. Colloquium Comput. Complex., 2003

Randomized Time-Space Tradeoffs for Directed Graph Connectivity.

Parikshit Gopalan, Richard J. Lipton, Aranyak Mehta

Proceedings of the FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science, 2003

Symmetric Polynomials over Z_m and Simultaneous Communication Protocol.

Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton

Proceedings of the 44th Symposium on Foundations of Computer Science, 2003

2002

Caching with expiration times.

Parikshit Gopalan, Howard J. Karloff, Aranyak Mehta, Milena Mihail, Nisheeth K. Vishnoi

Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002