Eli Ben-Sasson

According to our database, Eli Ben-Sasson authored at least 106 papers between 1999 and 2023.

Collaborative distances:

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

2023

Proximity Gaps for Reed-Solomon Codes.

Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, Shubhangi Saraf

J. ACM, October, 2023

Early childhood tracking application: Correspondence between crowd-based developmental percentiles and clinical tools.

Ayelet Ben-Sasson, Kayla Jacobs, Eli Ben-Sasson

Health Informatics J., January, 2023

Elliptic Curve Fast Fourier Transform (ECFFT) Part I: Low-degree Extension in Time <i>O(n</i> log <i>n</i>) over all Finite Fields.

Eli Ben-Sasson, Dan Carmon, Swastik Kopparty, David Levit

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

2022

Scalable and Transparent Proofs over All Large Fields, via Elliptic Curves (ECFFT part II).

Eli Ben-Sasson, Dan Carmon, Swastik Kopparty, David Levit

IACR Cryptol. ePrint Arch., 2022

Scalable and Transparent Proofs over All Large Fields, via Elliptic Curves.

Eli Ben-Sasson, Dan Carmon, Swastik Kopparty, David Levit

Electron. Colloquium Comput. Complex., 2022

2021

Elliptic Curve Fast Fourier Transform (ECFFT) Part I: Fast Polynomial Algorithms over all Finite Fields.

Eli Ben-Sasson, Dan Carmon, Swastik Kopparty, David Levit

Electron. Colloquium Comput. Complex., 2021

2020

Design of Symmetric-Key Primitives for Advanced Cryptographic Protocols.

Abdelrahaman Aly, Tomer Ashur, Eli Ben-Sasson, Siemen Dhooghe, Alan Szepieniec

IACR Trans. Symmetric Cryptol., 2020

STARK Friendly Hash - Survey and Recommendation.

Eli Ben-Sasson, Lior Goldberg, David Levit

IACR Cryptol. ePrint Arch., 2020

2019

Linear-Size Constant-Query IOPs for Delegating Computation.

Eli Ben-Sasson, Alessandro Chiesa, Lior Goldberg, Tom Gur, Michael Riabzev, Nicholas Spooner

IACR Cryptol. ePrint Arch., 2019

Efficient Symmetric Primitives for Advanced Cryptographic Protocols (A Marvellous Contribution).

Abdelrahaman Aly, Tomer Ashur, Eli Ben-Sasson, Siemen Dhooghe, Alan Szepieniec

IACR Cryptol. ePrint Arch., 2019

DEEP-FRI: Sampling Outside the Box Improves Soundness.

Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, Shubhangi Saraf

Electron. Colloquium Comput. Complex., 2019

The Complexity of User Retention.

Eli Ben-Sasson, Eden Saig

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

Scalable Zero Knowledge with No Trusted Setup.

Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, Michael Riabzev

Proceedings of the Advances in Cryptology - CRYPTO 2019, 2019

Evaluating Expert Curation in a Baby Milestone Tracking App.

Ayelet Ben-Sasson, Eli Ben-Sasson, Kayla Jacobs, Elisheva Rotman Argaman, Eden Saig

Proceedings of the 2019 CHI Conference on Human Factors in Computing Systems, 2019

2018

Aurora: Transparent Succinct Arguments for R1CS.

Eli Ben-Sasson, Alessandro Chiesa, Michael Riabzev, Nicholas Spooner, Madars Virza, Nicholas P. Ward

IACR Cryptol. ePrint Arch., 2018

Scalable, transparent, and post-quantum secure computational integrity.

Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, Michael Riabzev

IACR Cryptol. ePrint Arch., 2018

Worst-case to average case reductions for the distance to a code.

Eli Ben-Sasson, Swastik Kopparty, Shubhangi Saraf

Electron. Colloquium Comput. Complex., 2018

Brief Announcement: Towards an Abstract Model of User Retention Dynamics.

Eli Ben-Sasson, Eden Saig

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

2017

Collaborative Discovery: A study of Guru-follower dynamics.

Eli Ben-Sasson, Eden Saig

Electron. Colloquium Comput. Complex., 2017

Fast Reed-Solomon Interactive Oracle Proofs of Proximity.

Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, Michael Riabzev

Electron. Colloquium Comput. Complex., 2017

Sparse affine-invariant linear codes are locally testable.

Eli Ben-Sasson, Noga Ron-Zewi, Madhu Sudan

Comput. Complex., 2017

Scalable Zero Knowledge Via Cycles of Elliptic Curves.

Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, Madars Virza

Algorithmica, 2017

Zero Knowledge Protocols from Succinct Constraint Detection.

Eli Ben-Sasson, Alessandro Chiesa, Michael A. Forbes, Ariel Gabizon, Michael Riabzev, Nicholas Spooner

Proceedings of the Theory of Cryptography - 15th International Conference, 2017

Baby CROINC: an online, crowd-based, expert-curated system for monitoring child development.

Ayelet Ben-Sasson, Eli Ben-Sasson, Kayla Jacobs, Eden Saig

Proceedings of the 11th EAI International Conference on Pervasive Computing Technologies for Healthcare, 2017

Interactive Oracle Proofs with Constant Rate and Query Complexity.

Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Michael Riabzev, Nicholas Spooner

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016

Subspace Polynomials and Cyclic Subspace Codes.

Eli Ben-Sasson, Tuvi Etzion, Ariel Gabizon, Netanel Raviv

IEEE Trans. Inf. Theory, 2016

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

Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir, Henning Stichtenoth

J. ACM, 2016

Interactive Oracle Proofs.

Eli Ben-Sasson, Alessandro Chiesa, Nicholas Spooner

IACR Cryptol. ePrint Arch., 2016

Computational integrity with a public random string from quasi-linear PCPs.

Eli Ben-Sasson, Iddo Bentov, Alessandro Chiesa, Ariel Gabizon, Daniel Genkin, Matan Hamilis, Evgenya Pergament, Michael Riabzev, Mark Silberstein, Eran Tromer, Madars Virza

IACR Cryptol. ePrint Arch., 2016

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

Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Madars Virza

Electron. Colloquium Comput. Complex., 2016

Short Interactive Oracle Proofs with Constant Query Complexity, via Composition and Sumcheck.

Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Michael Riabzev, Nicholas Spooner

Electron. Colloquium Comput. Complex., 2016

On Probabilistic Checking in Perfect Zero Knowledge.

Eli Ben-Sasson, Alessandro Chiesa, Michael A. Forbes, Ariel Gabizon, Michael Riabzev, Nicholas Spooner

Electron. Colloquium Comput. Complex., 2016

A security analysis of Probabilistically Checkable Proofs.

Eli Ben-Sasson, Iddo Bentov, Ariel Gabizon, Michael Riabzev

Electron. Colloquium Comput. Complex., 2016

Improved concrete efficiency and security analysis of Reed-Solomon PCPPs.

Eli Ben-Sasson, Iddo Bentov, Ariel Gabizon, Michael Riabzev

Electron. Colloquium Comput. Complex., 2016

Fast Multiplication in Binary Fields on GPUs via Register Cache.

Eli Ben-Sasson, Matan Hamilis, Mark Silberstein, Eran Tromer

Proceedings of the 2016 International Conference on Supercomputing, 2016

2015

On the information leakage of public-output protocols.

Eli Ben-Sasson, Gal Maor

Electron. Colloquium Comput. Complex., 2015

Lower bound for communication complexity with no public randomness.

Eli Ben-Sasson, Gal Maor

Electron. Colloquium Comput. Complex., 2015

On Public Key Encryption from Noisy Codewords.

Eli Ben-Sasson, Iddo Bentov, Ivan Bjerre Damgård, Yuval Ishai, Noga Ron-Zewi

Electron. Colloquium Comput. Complex., 2015

Composition of semi-LTCs by two-wise tensor products.

Eli Ben-Sasson, Michael Viderman

Comput. Complex., 2015

Secure Sampling of Public Parameters for Succinct Zero Knowledge Proofs.

Eli Ben-Sasson, Alessandro Chiesa, Matthew Green, Eran Tromer, Madars Virza

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

2014

An Additive Combinatorics Approach Relating Rank to Communication Complexity.

Eli Ben-Sasson, Shachar Lovett, Noga Ron-Zewi

J. ACM, 2014

Zerocash: Decentralized Anonymous Payments from Bitcoin.

Eli Ben-Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, Madars Virza

IACR Cryptol. ePrint Arch., 2014

Short PCPs with projection queries.

Eli Ben-Sasson, Emanuele Viola

Electron. Colloquium Comput. Complex., 2014

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

Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, Madars Virza

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

2013

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

Eli Ben-Sasson, Ariel Gabizon

Theory Comput., 2013

Succinct Non-Interactive Arguments for a von Neumann Architecture.

Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, Madars Virza

IACR Cryptol. ePrint Arch., 2013

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

Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer, Madars Virza

IACR Cryptol. ePrint Arch., 2013

On the concrete efficiency of probabilistically-checkable proofs.

Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer

Proceedings of the Symposium on Theory of Computing Conference, 2013

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

Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer

Proceedings of the Innovations in Theoretical Computer Science, 2013

2012

Fast Reductions from RAMs to Delegatable Succinct Constraint Satisfaction Problems.

Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer

IACR Cryptol. ePrint Arch., 2012

A Combinatorial Characterization of smooth LTCs and Applications.

Eli Ben-Sasson, Michael Viderman

Electron. Colloquium Comput. Complex., 2012

Sampling-based proofs of almost-periodicity results and algorithmic applications.

Eli Ben-Sasson, Noga Ron-Zewi, Madhur Tulsiani, Julia Wolf

Electron. Colloquium Comput. Complex., 2012

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

Eli Ben-Sasson, Ariel Gabizon, Yohay Kaplan, Swastik Kopparty, Shubhangi Saraf

Electron. Colloquium Comput. Complex., 2012

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

Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer

Electron. Colloquium Comput. Complex., 2012

Towards lower bounds on locally testable codes via density arguments.

Eli Ben-Sasson, Michael Viderman

Comput. Complex., 2012

2011

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

Eli Ben-Sasson, Serge Fehr, Rafail Ostrovsky

IACR Cryptol. ePrint Arch., 2011

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

Eli Ben-Sasson, Shachar Lovett, Noga Zewi

Electron. Colloquium Comput. Complex., 2011

On Sums of Locally Testable Affine Invariant Properties.

Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka, Madhu Sudan

Electron. Colloquium Comput. Complex., 2011

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

Eli Ben-Sasson, Ariel Gabizon

Electron. Colloquium Comput. Complex., 2011

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

Eli Ben-Sasson, Jan Johannsen

Proceedings of the IJCAI 2011, 2011

2010

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

Eli Ben-Sasson, Prahladh Harsha

ACM Trans. Comput. Log., 2010

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

Eli Ben-Sasson, Swastik Kopparty, Jaikumar Radhakrishnan

IEEE Trans. Inf. Theory, 2010

From Affine to Two-Source Extractors via Approximate Duality.

Eli Ben-Sasson, Noga Zewi

Electron. Colloquium Comput. Complex., 2010

Low Rate Is Insufficient for Local Testability.

Eli Ben-Sasson, Michael Viderman

Electron. Colloquium Comput. Complex., 2010

Limits on the rate of locally testable affine-invariant codes.

Eli Ben-Sasson, Madhu Sudan

Electron. Colloquium Comput. Complex., 2010

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

Eli Ben-Sasson, Jakob Nordström

Electron. Colloquium Comput. Complex., 2010

Symmetric LDPC codes are not necessarily locally testable.

Eli Ben-Sasson, Ghid Maatouk, Amir Shpilka, Madhu Sudan

Electron. Colloquium Comput. Complex., 2010

Affine Dispersers from Subspace Polynomials.

Eli Ben-Sasson, Swastik Kopparty

Electron. Colloquium Comput. Complex., 2010

Lower bounds for width-restricted clause learning on small width formulas.

Eli Ben-Sasson, Jan Johannsen

Electron. Colloquium Comput. Complex., 2010

Limitation on the rate of families of locally testable codes.

Eli Ben-Sasson

Electron. Colloquium Comput. Complex., 2010

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

Shir Ben-Israel, Eli Ben-Sasson, David R. Karger

Electron. Colloquium Comput. Complex., 2010

Random Cnf's are Hard for the Polynomial Calculus.

Eli Ben-Sasson, Russell Impagliazzo

Comput. Complex., 2010

Limitation on the Rate of Families of Locally Testable Codes.

Eli Ben-Sasson

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

2009

Tensor Products of Weakly Smooth Codes are Robust.

Eli Ben-Sasson, Michael Viderman

Theory Comput., 2009

A Space Hierarchy for k-DNF Resolution.

Eli Ben-Sasson, Jakob Nordström

Electron. Colloquium Comput. Complex., 2009

Understanding Space in Resolution: Optimal Lower Bounds and Exponential Trade-offs.

Eli Ben-Sasson, Jakob Nordström

Electron. Colloquium Comput. Complex., 2009

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

Eli Ben-Sasson, Jakob Nordström

Electron. Colloquium Comput. Complex., 2009

Locally Testable Codes Require Redundant Testers.

Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman

Electron. Colloquium Comput. Complex., 2009

2008

Short PCPs with Polylog Query Complexity.

Eli Ben-Sasson, Madhu Sudan

SIAM J. Comput., 2008

2007

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

Mikhail Alekhnovich, Eli Ben-Sasson

SIAM J. Comput., 2007

Sound 3-query PCPPs are Long.

Arie Matsliah, Eli Ben-Sasson, Prahladh Harsha, Oded Lachish

Electron. Colloquium Comput. Complex., 2007

2006

An Approach to Bounded Rationality.

Eli Ben-Sasson, 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.

Eli Ben-Sasson, Swastik Kopparty, Jaikumar Radhakrishnan

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

2005

Some 3CNF Properties Are Hard to Test.

Eli Ben-Sasson, Prahladh Harsha, Sofya Raskhodnikova

SIAM J. Comput., 2005

Short PCPs Verifiable in Polylogarithmic Time.

Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan

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

2004

Simple PCPs with Poly-log Rate and Query Complexity

Eli Ben-Sasson, Madhu Sudan

Electron. Colloquium Comput. Complex., 2004

Robust Locally Testable Codes and Products of Codes

Eli Ben-Sasson, Madhu Sudan

Electron. Colloquium Comput. Complex., 2004

Robust PCPs of Proximity, Shorter PCPs and Applications to Coding

Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan

Electron. Colloquium Comput. Complex., 2004

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

Michael Alekhnovich, Eli Ben-Sasson

Electron. Colloquium Comput. Complex., 2004

Near Optimal Separation Of Tree-Like And General Resolution.

Eli Ben-Sasson, Russell Impagliazzo, Avi Wigderson

Comb., 2004

2003

Bounds on 2-Query Codeword Testing.

Eli Ben-Sasson, Oded Goldreich, Madhu Sudan

Electron. Colloquium Comput. Complex., 2003

3CNF Properties are Hard to Test

Eli Ben-Sasson, Prahladh Harsha, Sofya Raskhodnikova

Electron. Colloquium Comput. Complex., 2003

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

Eli Ben-Sasson, Prahladh Harsha

Electron. Colloquium Comput. Complex., 2003

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

Eli Ben-Sasson, Madhu Sudan, Salil P. Vadhan, Avi Wigderson

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

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

Michael Alekhnovich, Eli Ben-Sasson

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

2002

A Gap in Average Proof Complexity

Eli Ben-Sasson, Yonatan Bilu

Electron. Colloquium Comput. Complex., 2002

Hard examples for the bounded depth Frege proof system.

Eli Ben-Sasson

Comput. Complex., 2002

Hard examples for bounded depth frege.

Eli Ben-Sasson

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

Size space tradeoffs for resolution.

Eli Ben-Sasson

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

2001

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

Eli Ben-Sasson

PhD thesis, 2001

Short proofs are narrow - resolution made simple.

Eli Ben-Sasson, Avi Wigderson

J. ACM, 2001

Space Complexity of Random Formulae in Resolution

Eli Ben-Sasson, Nicola Galesi

Electron. Colloquium Comput. Complex., 2001

2000

Pseudorandom Generators in Propositional Proof Complexity

Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson

Electron. Colloquium Comput. Complex., 2000

Near-Optimal Separation of Treelike and General Resolution

Eli Ben-Sasson, Russell Impagliazzo, Avi Wigderson

Electron. Colloquium Comput. Complex., 2000

1999

Space Complexity in Propositional Calculus

Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson

Electron. Colloquium Comput. Complex., 1999

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

Eli Ben-Sasson, Avi Wigderson

Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999