# Boaz Barak

According to our database

Collaborative distances:

^{1}, Boaz Barak authored at least 86 papers between 1999 and 2019.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### Homepage:

#### On csauthors.net:

## Bibliography

2019

Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture.

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Sum-of-Squares Meets Program Obfuscation, Revisited.

Proceedings of the Advances in Cryptology - EUROCRYPT 2019, 2019

2018

Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation).

Proceedings of the Advances in Cryptology - EUROCRYPT 2018 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29, 2018

2017

Merkle's Key Agreement Protocol is Optimal: An O(n

^{2}) Attack on Any Key Agreement from Random Oracles.
J. Cryptology, 2017

The Complexity of Public-Key Cryptography.

IACR Cryptology ePrint Archive, 2017

The Complexity of Public-Key Cryptograph.

Electronic Colloquium on Computational Complexity (ECCC), 2017

Quantum entanglement, sum of squares, and the log rank conjecture.

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

The Complexity of Public-Key Cryptography.

Proceedings of the Tutorials on the Foundations of Cryptography., 2017

2016

Hopes, Fears and Software Obfuscation: A Survey.

IACR Cryptology ePrint Archive, 2016

Computer science should stay young.

Commun. ACM, 2016

A breakthrough in software obfuscation: technical perspective.

Commun. ACM, 2016

Hopes, fears, and software obfuscation.

Commun. ACM, 2016

A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem.

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

Noisy Tensor Completion via the Sum-of-Squares Hierarchy.

Proceedings of the 29th Conference on Learning Theory, 2016

2015

Path-Quality Monitoring in the Presence of Adversaries: The Secure Sketch Protocols.

IEEE/ACM Trans. Netw., 2015

Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method.

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Sum of Squares Lower Bounds from Pairwise Independence.

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Convexity, Bayesianism, and the Quest Towards Optimal Algorithms (Invited Talk).

Proceedings of the 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, 2015

Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree.

Proceedings of the Approximation, 2015

2014

Sum-of-squares proofs and the quest toward optimal algorithms.

Electronic Colloquium on Computational Complexity (ECCC), 2014

Structure vs Combinatorics in Computational Complexity.

Bulletin of the EATCS, 2014

Obfuscation for Evasive Functions.

Proceedings of the Theory of Cryptography - 11th Theory of Cryptography Conference, 2014

Rounding sum-of-squares relaxations.

Proceedings of the Symposium on Theory of Computing, 2014

Protecting Obfuscation against Algebraic Attacks.

Proceedings of the Advances in Cryptology - EUROCRYPT 2014, 2014

2013

Structure vs Combinatorics in Computational Complexity.

Electronic Colloquium on Computational Complexity (ECCC), 2013

Special Issue "Conference on Computational Complexity 2012" Guest editors' foreword.

Computational Complexity, 2013

On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction.

Proceedings of the Innovations in Theoretical Computer Science, 2013

2012

Proof vs. Truth in Computational Complexity.

Electronic Colloquium on Computational Complexity (ECCC), 2012

Truth vs. Proof in Computational Complexity.

Bulletin of the EATCS, 2012

Hypercontractivity, sum-of-squares proofs, and their applications.

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Making the Long Code Shorter.

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

2011

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

Electronic Colloquium on Computational Complexity (ECCC), 2011

Computational complexity and information asymmetry in financial products.

Commun. ACM, 2011

Rank bounds for design matrices with applications toc ombinatorial geometry and locally correctable codes.

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

Subsampling Mathematical Relaxations and Average-case Complexity.

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Rounding Semidefinite Programming Hierarchies via Global Correlation.

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

Leftover Hash Lemma, Revisited.

Proceedings of the Advances in Cryptology - CRYPTO 2011, 2011

2010

Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes.

Electronic Colloquium on Computational Complexity (ECCC), 2010

How to compress interactive communication.

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Public-key cryptography from different assumptions.

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Computational Complexity and Information Asymmetry in Financial Products (Extended Abstract).

Proceedings of the Innovations in Computer Science, 2010

Subexponential Algorithms for Unique Games and Related Problems.

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

Bounded Key-Dependent Message Security.

Proceedings of the Advances in Cryptology - EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Monaco / French Riviera, May 30, 2010

2009

Subsampling Semidefinite Programs and Max-Cut on the Sphere.

Electronic Colloquium on Computational Complexity (ECCC), 2009

Direct Sums in Randomized Communication Complexity.

Electronic Colloquium on Computational Complexity (ECCC), 2009

The uniform hardcore lemma via approximate Bregman projections.

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

Merkle Puzzles Are Optimal - An

*O*(*n*^{2})-Query Attack on Any Key Exchange from a Random Oracle.
Proceedings of the Advances in Cryptology, 2009

Strong Parallel Repetition Theorem for Free Projection Games.

Proceedings of the Approximation, 2009

Computational Complexity - A Modern Approach.

Cambridge University Press, ISBN: 978-0-521-42426-4, 2009

2008

Public Key Cryptography from Different Assumptions.

IACR Cryptology ePrint Archive, 2008

Merkle Puzzles are Optimal.

IACR Cryptology ePrint Archive, 2008

Path-quality monitoring in the presence of adversaries.

Proceedings of the 2008 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, 2008

Rounding Parallel Repetitions of Unique Games.

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

On Basing Lower-Bounds for Learning on Worst-Case Assumptions.

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

Protocols and Lower Bounds for Failure Localization in the Internet.

Proceedings of the Advances in Cryptology, 2008

2007

Privacy, accuracy, and consistency too: a holistic solution to contingency table release.

Proceedings of the Twenty-Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2007

Lower Bounds on Signatures From Symmetric Primitives.

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

2006

2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction.

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Concurrent Non-Malleable Zero Knowledge.

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

Non-black-box Techniques in Cryptography.

Proceedings of the Computer Science, 2006

2005

Derandomization in Cryptography

Electronic Colloquium on Computational Complexity (ECCC), 2005

How To Play Almost Any Mental Game Over The Net - Concurrent Composition via Super-Polynomial Simulation

Electronic Colloquium on Computational Complexity (ECCC), 2005

Simulating independence: new constructions of condensers, ramsey graphs, dispersers, and extractors.

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

How To Play Almost Any Mental Game Over The Net - Concurrent Composition via Super-Polynomial Simulation.

Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

Secure Computation Without Authentication.

Proceedings of the Advances in Cryptology, 2005

A model and architecture for pseudo-random generation with applications to /dev/random.

Proceedings of the 12th ACM Conference on Computer and Communications Security, 2005

2004

Protocol Initialization for the Framework of Universal Composability.

IACR Cryptology ePrint Archive, 2004

Lower Bounds for Non-Black-Box Zero Knowledge

Electronic Colloquium on Computational Complexity (ECCC), 2004

On the Possibility of One-Message Weak Zero-Knowledge.

Proceedings of the Theory of Cryptography, First Theory of Cryptography Conference, 2004

Extracting Randomness Using Few Independent Sources.

Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

Universally Composable Protocols with Relaxed Set-Up Assumptions.

Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

2003

Computational Analogues of Entropy.

Proceedings of the Approximation, 2003

Lower Bounds for Non-Black-Box Zero Knowledge.

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

Derandomization in Cryptography.

Proceedings of the Advances in Cryptology, 2003

True Random Number Generators Secure in a Changing Environment.

Proceedings of the Cryptographic Hardware and Embedded Systems, 2003

2002

Strict Polynomial-time in Simulation and Extraction

Electronic Colloquium on Computational Complexity (ECCC), 2002

Strict polynomial-time in simulation and extraction.

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

A Probabilistic-Time Hierarchy Theorem for "Slightly Non-uniform" Algorithms.

Proceedings of the Randomization and Approximation Techniques, 6th International Workshop, 2002

Constant-Round Coin-Tossing with a Man in the Middle or Realizing the Shared Random String Model.

Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

Universal Arguments and their Applications.

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

2001

On the (Im)possibility of Obfuscating Programs

Electronic Colloquium on Computational Complexity (ECCC), 2001

Resettably-Sound Zero-Knowledge and its Applications.

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

How to Go Beyond the Black-Box Simulation Barrier.

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

On the (Im)possibility of Obfuscating Programs.

Proceedings of the Advances in Cryptology, 2001

2000

Clock synchronization with faults and recoveries (extended abstract).

Proceedings of the Nineteenth Annual ACM Symposium on Principles of Distributed Computing, 2000

1999

The Proactive Security Toolkit and Applications.

Proceedings of the CCS '99, 1999