# Parikshit Gopalan

According to our database

Collaborative distances:

^{1}, Parikshit Gopalan authored at least 91 papers between 2002 and 2018.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### On csauthors.net:

## Bibliography

2018

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

ACM Trans. Economics and Comput., 2018

Pseudorandomness via the Discrete Fourier Transform.

SIAM J. Comput., 2018

Stable and Consistent Membership at Scale with Rapid.

Proceedings of the 2018 USENIX Annual Technical Conference, 2018

Efficient Anomaly Detection via Matrix Sketching.

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.

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

2016

Degree and Sensitivity: tails of two distributions.

Electronic Colloquium on Computational Complexity (ECCC), 2016

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

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

Degree and Sensitivity: Tails of Two Distributions.

Proceedings of the 31st Conference on Computational Complexity, 2016

2015

Making the Long Code Shorter.

SIAM J. Comput., 2015

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

Electronic Colloquium on Computational Complexity (ECCC), 2015

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

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

Pseudorandomness via the Discrete Fourier Transform.

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

2014

Explicit Maximally Recoverable Codes With Locality.

IEEE Trans. Information Theory, 2014

Inequalities and tail bounds for elementary symmetric polynomials.

Electronic Colloquium on Computational Complexity (ECCC), 2014

Constructing Ramsey graphs from Boolean function representations.

Combinatorica, 2014

Locally testable codes and cayley graphs.

Proceedings of the Innovations in Theoretical Computer Science, 2014

2013

A Fourier-Analytic Approach to Reed-Muller Decoding.

IEEE Trans. Information Theory, 2013

Pseudorandom Generators for Combinatorial Shapes.

SIAM J. Comput., 2013

Locally Testable Codes and Cayley Graphs.

Electronic Colloquium on Computational Complexity (ECCC), 2013

Explicit Maximally Recoverable Codes with Locality.

Electronic Colloquium on Computational Complexity (ECCC), 2013

DNF sparsification and a faster deterministic counting algorithm.

Computational Complexity, 2013

Zombie memory: extending memory lifetime by reviving dead blocks.

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

2012

On the Locality of Codeword Symbols.

IEEE Trans. Information Theory, 2012

Learning Functions of Halfspaces using Prefix Covers.

Proceedings of the COLT 2012, 2012

Better pseudorandom generators from milder pseudorandom restrictions.

Electronic Colloquium on Computational Complexity (ECCC), 2012

DNF Sparsification and a Faster Deterministic Counting.

Electronic Colloquium on Computational Complexity (ECCC), 2012

Erasure Coding in Windows Azure Storage.

Proceedings of the 2012 USENIX Annual Technical Conference, 2012

Better Pseudorandom Generators from Milder Pseudorandom Restrictions.

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

Making the Long Code Shorter.

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

DNF Sparsification and a Faster Deterministic Counting Algorithm.

Proceedings of the 27th Conference on Computational Complexity, 2012

2011

Testing Fourier Dimensionality and Sparsity.

SIAM J. Comput., 2011

List Decoding Tensor Products and Interleaved Codes.

SIAM J. Comput., 2011

Matching Vector Codes.

SIAM J. Comput., 2011

Hardness amplification within NP against deterministic algorithms.

J. Comput. Syst. Sci., 2011

On the Locality of Codeword Symbols.

Electronic Colloquium on Computational Complexity (ECCC), 2011

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

Electronic Colloquium on Computational Complexity (ECCC), 2011

Pseudorandom generators for combinatorial shapes.

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

An FPTAS for #Knapsack and Related Counting Problems.

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

2010

Hardness of Reconstructing Multivariate Polynomials over Finite Fields.

SIAM J. Comput., 2010

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

SIAM J. Comput., 2010

Bounded Independence Fools Halfspaces.

SIAM J. Comput., 2010

Fooling functions of halfspaces under product distributions.

Electronic Colloquium on Computational Complexity (ECCC), 2010

Learning and Lower Bounds for AC

^{0}with Threshold Gates.
Electronic Colloquium on Computational Complexity (ECCC), 2010

Pseudorandom Generators for Combinatorial Shapes.

Electronic Colloquium on Computational Complexity (ECCC), 2010

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

Electronic Colloquium on Computational Complexity (ECCC), 2010

Matching Vector Codes.

Electronic Colloquium on Computational Complexity (ECCC), 2010

The Complexity of Boolean Functions in Different Characteristics.

Computational Complexity, 2010

A Fourier-Analytic Approach to Reed-Muller Decoding.

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

Matching Vector Codes.

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

Fooling Functions of Halfspaces under Product Distributions.

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

Learning and Lower Bounds for AC

^{0}with Threshold Gates.
Proceedings of the Approximation, 2010

2009

The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies.

SIAM J. Comput., 2009

On Agnostic Learning of Parities, Monomials, and Halfspaces.

SIAM J. Comput., 2009

On the Complexity of Boolean Functions in Different Characteristics.

Electronic Colloquium on Computational Complexity (ECCC), 2009

A note on Efremenko's Locally Decodable Codes.

Electronic Colloquium on Computational Complexity (ECCC), 2009

A Fourier-analytic approach to Reed-Muller decoding.

Electronic Colloquium on Computational Complexity (ECCC), 2009

Bounded Independence Fools Halfspaces.

Electronic Colloquium on Computational Complexity (ECCC), 2009

List decoding tensor products and interleaved codes.

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

Finding duplicates in a data stream.

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

Testing Fourier Dimensionality and Sparsity.

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

Bounded Independence Fools Halfspaces.

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

On the Complexity of Boolean Functions in Different Characteristics.

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

2008

Query-Efficient Algorithms for Polynomial Interpolation over Composites.

SIAM J. Comput., 2008

List Decoding Tensor Products and Interleaved Codes.

Electronic Colloquium on Computational Complexity (ECCC), 2008

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

Computational Complexity, 2008

Algorithms for Modular Counting of Roots of Multivariate Polynomials.

Algorithmica, 2008

List-decoding reed-muller codes over small fields.

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

Agnostically learning decision trees.

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

A Query Algorithm for Agnostically Learning DNF?.

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

Hardness Amplification within NP against Deterministic Algorithms.

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

2007

Hardness of Reconstructing Multivariate Polynomials over Finite Fields.

Electronic Colloquium on Computational Complexity (ECCC), 2007

Deterministic Hardness Amplification via Local GMD Decoding.

Electronic Colloquium on Computational Complexity (ECCC), 2007

Estimating the sortedness of a data stream.

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

Hardness of Reconstructing Multivariate Polynomials over Finite Fields.

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

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

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

2006

Symmetric polynomials over Z

_{m}and simultaneous communication protocols.
J. Comput. Syst. Sci., 2006

The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies.

Electronic Colloquium on Computational Complexity (ECCC), 2006

New Results for Learning Noisy Parities and Halfspaces.

Electronic Colloquium on Computational Complexity (ECCC), 2006

Query-efficient algorithms for polynomial interpolation over composites.

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

Algorithms for Modular Counting of Roots of Multivariate Polynomials.

Proceedings of the LATIN 2006: Theoretical Informatics, 2006

The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies.

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

New Results for Learning Noisy Parities and Halfspaces.

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

Constructing Ramsey Graphs from Boolean Function Representations.

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

2005

Caching with Expiration Times for Internet Applications.

Internet Mathematics, 2005

Constructing Ramsey Graphs from Boolean Function Representations

Electronic Colloquium on Computational Complexity (ECCC), 2005

2004

The Degree of Threshold Mod 6 and Diophantine Equations

Electronic Colloquium on Computational Complexity (ECCC), 2004

Polynomials That Sign Represent Parity and Descartes Rule of Signs.

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

2003

Symmetric Polynomials over Z

_{m}and Simultaneous Communication Protocols
Electronic Colloquium on Computational Complexity (ECCC), 2003

Randomized Time-Space Tradeoffs for Directed Graph Connectivity.

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

Symmetric Polynomials over Z

_{m}and Simultaneous Communication Protocol.
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

2002

Caching with expiration times.

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