Eli Ben-Sasson

Alessandro Chiesa

Nicholas Spooner

Proceedings of the Theory of Cryptography - 14th International Conference, 2016

Quasi-Linear Size Zero Knowledge from Linear-Algebraic PCPs.

[BibT_eX]

[DOI]

Proceedings of the Theory of Cryptography - 13th International Conference, 2016

On Public Key Encryption from Noisy Codewords.

[BibT_eX]

[DOI]

Proceedings of the Public-Key Cryptography - PKC 2016, 2016

Fast Multiplication in Binary Fields on GPUs via Register Cache.

[BibT_eX]

[DOI]

Proceedings of the 2016 International Conference on Supercomputing, 2016

2015

On the information leakage of public-output protocols.

[BibT_eX]

[DOI]

Gal Maor

Electron. Colloquium Comput. Complex., 2015

Lower bound for communication complexity with no public randomness.

[BibT_eX]

[DOI]

Gal Maor

Electron. Colloquium Comput. Complex., 2015

Secure Sampling of Public Parameters for Succinct Zero Knowledge Proofs.

[BibT_eX]

[DOI]

Proceedings of the 2015 IEEE Symposium on Security and Privacy, 2015

Subspace polynomials and cyclic subspace codes.

[BibT_eX]

[DOI]

Proceedings of the IEEE International Symposium on Information Theory, 2015

2014

Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture.

[BibT_eX]

[DOI]

Proceedings of the 23rd USENIX Security Symposium, San Diego, CA, USA, August 20-22, 2014., 2014

Zerocash: Decentralized Anonymous Payments from Bitcoin.

[BibT_eX]

[DOI]

Proceedings of the 2014 IEEE Symposium on Security and Privacy, 2014

Short PCPs with Projection Queries.

[BibT_eX]

[DOI]

Emanuele Viola

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Sampling-Based Proofs of Almost-Periodicity Results and Algorithmic Applications.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Scalable Zero Knowledge via Cycles of Elliptic Curves.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology - CRYPTO 2014, 2014

2013

Extractors for Polynomial Sources over Fields of Constant Order and Small Characteristic.

[BibT_eX]

[DOI]

Ariel Gabizon

Theory Comput., 2013

Succinct Non-Interactive Arguments for a von Neumann Architecture.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2013

A new family of locally correctable codes based on degree-lifted algebraic geometry codes.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing Conference, 2013

On the concrete efficiency of probabilistically-checkable proofs.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing Conference, 2013

Fast reductions from RAMs to delegatable succinct constraint satisfaction problems: extended abstract.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Theoretical Computer Science, 2013

Constant Rate PCPs for Circuit-SAT with Sublinear Query Complexity.

[BibT_eX]

[DOI]

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology - CRYPTO 2013, 2013

2012

Fast Reductions from RAMs to Delegatable Succinct Constraint Satisfaction Problems.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2012

A Combinatorial Characterization of smooth LTCs and Applications.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

On the Concrete-Efficiency Threshold of Probabilistically-Checkable Proofs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Sparse Affine-Invariant Linear Codes Are Locally Testable.

[BibT_eX]

[DOI]

Noga Ron-Zewi

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

An Additive Combinatorics Approach Relating Rank to Communication Complexity.

[BibT_eX]

[DOI]

Shachar Lovett

Noga Ron-Zewi

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

Near-Linear Unconditionally-Secure Multiparty Computation with a Dishonest Minority.

[BibT_eX]

[DOI]

Serge Fehr

Rafail Ostrovsky

Proceedings of the Advances in Cryptology - CRYPTO 2012, 2012

Extractors for Polynomials Sources over Constant-Size Fields of Small Characteristic.

[BibT_eX]

[DOI]

Ariel Gabizon

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011

An additive combinatorics approach to the log-rank conjecture in communication complexity.

[BibT_eX]

[DOI]

Shachar Lovett

Noga Zewi

Electron. Colloquium Comput. Complex., 2011

From affine to two-source extractors via approximate duality.

[BibT_eX]

[DOI]

Noga Zewi

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

Understanding Space in Proof Complexity: Separations and Trade-offs via Substitutions.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Computer Science, 2011

Lower Bounds for Width-Restricted Clause Learning on Formulas of Small Width.

[BibT_eX]

[DOI]

Jan Johannsen

Proceedings of the IJCAI 2011, 2011

Towards Lower Bounds on Locally Testable Codes via Density Arguments.

[BibT_eX]

[DOI]

Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011

Symmetric LDPC Codes are not Necessarily Locally Testable.

[BibT_eX]

[DOI]

Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011

Limits on the Rate of Locally Testable Affine-Invariant Codes.

[BibT_eX]

[DOI]

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

On Sums of Locally Testable Affine Invariant Properties.

[BibT_eX]

[DOI]

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010

Lower bounds for bounded depth Frege proofs via Pudlák-Buss games.

[BibT_eX]

[DOI]

ACM Trans. Comput. Log., 2010

Subspace polynomials and limits to list decoding of Reed-Solomon codes.

[BibT_eX]

[DOI]

Swastik Kopparty

Jaikumar Radhakrishnan

IEEE Trans. Inf. Theory, 2010

Limitation on the rate of families of locally testable codes.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

Breaking local symmetries can dramatically reduce the length of propositional refutations.

[BibT_eX]

[DOI]

Shir Ben-Israel

David R. Karger

Electron. Colloquium Comput. Complex., 2010

Lower Bounds for Width-Restricted Clause Learning on Small Width Formulas.

[BibT_eX]

[DOI]

Jan Johannsen

Proceedings of the Theory and Applications of Satisfiability Testing, 2010

Limitation on the Rate of Families of Locally Testable Codes.

[BibT_eX]

[DOI]

Proceedings of the Property Testing - Current Research and Surveys, 2010

Low Rate Is Insufficient for Local Testability.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2010

2009

A Space Hierarchy for k-DNF Resolution.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

Affine dispersers from subspace polynomials.

[BibT_eX]

[DOI]

Swastik Kopparty

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

Locally Testable Codes Require Redundant Testers.

[BibT_eX]

[DOI]

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

Composition of Semi-LTCs by Two-Wise Tensor Products.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2009

2008

Short PCPs with Polylog Query Complexity.

[BibT_eX]

[DOI]

SIAM J. Comput., 2008

Sound 3-Query PCPPs Are Long.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

Short Proofs May Be Spacious: An Optimal Separation of Space and Length in Resolution.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

Understanding space in resolution: optimal lower bounds and exponential trade-offs.

[BibT_eX]

[DOI]

Proceedings of the Computational Complexity of Discrete Problems, 14.09. - 19.09.2008, 2008

Tensor Products of Weakly Smooth Codes Are Robust.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2008

2007

Linear Upper Bounds for Random Walk on Small Density Random 3-CNFs.

[BibT_eX]

[DOI]

Mikhail Alekhnovich

SIAM J. Comput., 2007

2006

An Approach to Bounded Rationality.

[BibT_eX]

[DOI]

Adam Tauman Kalai

Ehud Kalai

Proceedings of the Advances in Neural Information Processing Systems 19, 2006

Subspace Polynomials and List Decoding of Reed-Solomon Codes.

[BibT_eX]

[DOI]

Swastik Kopparty

Jaikumar Radhakrishnan

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

2005

Simple PCPs with poly-log rate and query complexity.

[BibT_eX]

[DOI]

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Short PCPs Verifiable in Polylogarithmic Time.

[BibT_eX]

[DOI]

Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

2004

Linear Upper Bounds for Random Walk on Small Density Random 3CNFs

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2004

Near Optimal Separation Of Tree-Like And General Resolution.

[BibT_eX]

[DOI]

Russell Impagliazzo

Comb., 2004

Robust pcps of proximity, shorter pcps and applications to coding.

[BibT_eX]

[DOI]

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Robust Locally Testable Codes and Products of Codes.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2004

2003

3CNF Properties are Hard to Test

[BibT_eX]

[DOI]

Sofya Raskhodnikova

Electron. Colloquium Comput. Complex., 2003

Lower Bounds for Bounded-Depth Frege Proofs via Buss-Pudlack Games

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2003

Randomness-efficient low degree tests and short PCPs via epsilon-biased sets.

[BibT_eX]

[DOI]

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Some 3CNF properties are hard to test.

[BibT_eX]

[DOI]

Sofya Raskhodnikova

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Bounds on 2-Query Codeword Testing.

[BibT_eX]

[DOI]

Oded Goldreich

Proceedings of the Approximation, 2003

Linear Upper Bounds for Random Walk on Small Density Random 3-CNF.

[BibT_eX]

[DOI]

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

2002

A Gap in Average Proof Complexity

[BibT_eX]

[DOI]

Yonatan Bilu

Electron. Colloquium Comput. Complex., 2002

Hard examples for the bounded depth Frege proof system.

[BibT_eX]

[DOI]

Comput. Complex., 2002

Size space tradeoffs for resolution.

[BibT_eX]

[DOI]

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Hard Examples for Bounded Depth Frege.

[BibT_eX]

[DOI]

Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002

2001

Expansion in proof complexity. (הרחבה ומורכבות הוכחות.).

[BibT_eX]

[DOI]

PhD thesis, 2001

Space Complexity of Random Formulae in Resolution.

[BibT_eX]

[DOI]

Nicola Galesi

Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001

2000

Near-Optimal Separation of Treelike and General Resolution

[BibT_eX]

[DOI]

Russell Impagliazzo

Electron. Colloquium Comput. Complex., 2000

Space complexity in propositional calculus.

[BibT_eX]

[DOI]

Alexander A. Razborov

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Pseudorandom Generators in Propositional Proof Complexity.

[BibT_eX]

[DOI]

Alexander A. Razborov

Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

1999

Short Proofs are Narrow - Resolution Made Simple.

[BibT_eX]

[DOI]

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Random CNF's are Hard for the Polynomial Calculus.

[BibT_eX]

[DOI]

Russell Impagliazzo

Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

Short Proofs Are Narrow - Resolution Made Simple (Abstract).

[BibT_eX]

[DOI]