Parikshit Gopalan

According to our database, Parikshit Gopalan authored at least 77 papers between 2002 and 2024.

Collaborative distances:

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

2024

On Computationally Efficient Multi-Class Calibration.

Parikshit Gopalan, Lunjia Hu, Guy N. Rothblum

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

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

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

Parikshit Gopalan, Noam Nisan, Tim Roughgarden

ACM Trans. Economics and Comput., 2018

Pseudorandomness via the Discrete Fourier Transform.

Parikshit Gopalan, Daniel M. Kane, Raghu Meka

SIAM J. Comput., 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

Degree and Sensitivity: Tails of Two Distributions.

Parikshit Gopalan, Rocco A. Servedio, Avi Wigderson

Proceedings of the 31st Conference on Computational Complexity, 2016

2015

Making the Long Code Shorter.

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

SIAM J. Comput., 2015

Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions.

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

Electron. Colloquium Comput. Complex., 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

Constructing Ramsey graphs from Boolean function representations.

Parikshit Gopalan

Comb., 2014

2013

Locally Testable Codes and Cayley Graphs.

Parikshit Gopalan, Salil P. Vadhan, Yuan Zhou

Electron. Colloquium Comput. Complex., 2013

Explicit Maximally Recoverable Codes with Locality.

Parikshit Gopalan, Cheng Huang, Bob Jenkins, Sergey Yekhanin

Electron. Colloquium Comput. Complex., 2013

DNF sparsification and a faster deterministic counting algorithm.

Parikshit Gopalan, Raghu Meka, Omer Reingold

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

Better pseudorandom generators from milder pseudorandom restrictions.

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

Electron. Colloquium Comput. Complex., 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

2011

Testing Fourier Dimensionality and Sparsity.

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

SIAM J. Comput., 2011

Hardness amplification within NP against deterministic algorithms.

Parikshit Gopalan, Venkatesan Guruswami

J. Comput. Syst. Sci., 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

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

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

Anna Gál, Parikshit Gopalan

SIAM J. Comput., 2010

Fooling functions of halfspaces under product distributions.

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

Electron. Colloquium Comput. Complex., 2010

Learning and Lower Bounds for AC⁰ with Threshold Gates.

Parikshit Gopalan, Rocco A. Servedio

Electron. Colloquium Comput. Complex., 2010

Pseudorandom Generators for Combinatorial Shapes.

Parikshit Gopalan, Raghu Meka, Omer Reingold, David Zuckerman

Electron. Colloquium Comput. Complex., 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

Matching Vector Codes.

Zeev Dvir, Parikshit Gopalan, Sergey Yekhanin

Electron. Colloquium Comput. Complex., 2010

The Complexity of Boolean Functions in Different Characteristics.

Parikshit Gopalan, Amir Shpilka, Shachar Lovett

Comput. Complex., 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

A Fourier-analytic approach to Reed-Muller decoding.

Parikshit Gopalan

Electron. Colloquium Comput. Complex., 2009

Bounded Independence Fools Halfspaces.

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

Electron. Colloquium Comput. Complex., 2009

Finding duplicates in a data stream.

Parikshit Gopalan, Jaikumar Radhakrishnan

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

2008

Query-Efficient Algorithms for Polynomial Interpolation over Composites.

Parikshit Gopalan

SIAM J. Comput., 2008

List Decoding Tensor Products and Interleaved Codes.

Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra

Electron. Colloquium Comput. Complex., 2008

Polynomials that Sign Represent Parity and Descartes' Rule of Signs.

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

Comput. Complex., 2008

Algorithms for Modular Counting of Roots of Multivariate Polynomials.

Parikshit Gopalan, Venkatesan Guruswami, Richard J. Lipton

Algorithmica, 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

2007

Hardness of Reconstructing Multivariate Polynomials over Finite Fields.

Parikshit Gopalan, Subhash Khot, Rishi Saket

Electron. Colloquium Comput. Complex., 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

2006

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

Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton

J. Comput. Syst. Sci., 2006

The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies.

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

Electron. Colloquium Comput. Complex., 2006

New Results for Learning Noisy Parities and Halfspaces.

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

Electron. Colloquium Comput. Complex., 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

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 (FOCS 2003), 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