6 citations · 14 across the 5 of their papers we have counts for
7 papers
Elliptic Curve Fast Fourier Transform (ECFFT) Part I: Fast Polynomial Algorithms over all Finite Fields
Eli Ben-Sasson, Dan Carmon, Swastik Kopparty +1
For smooth finite fields (i.e., when factors into small primes) the Fast Fourier Transform (FFT) leads to the fastest known algebraic algorithms for many basic polynomi…
DEEP-FRI: Sampling outside the box improves soundness
Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty +1
Motivated by the quest for scalable and succinct zero knowledge arguments, we revisit worst-case-to-average-case reductions for linear spaces, raised by [Rothblum, Vadhan, Wigderso…
On Probabilistic Checking in Perfect Zero Knowledge
Eli Ben-Sasson, Alessandro Chiesa, Michael A. Forbes +3
We present the first constructions of single-prover proof systems that achieve perfect zero knowledge (PZK) for languages beyond NP, under no intractability assumptions: 1. The com…
Subspace Polynomials and Cyclic Subspace Codes
Eli Ben-Sasson, Tuvi Etzion, Ariel Gabizon +1
Subspace codes have received an increasing interest recently due to their application in error-correction for random network coding. In particular, cyclic subspace codes are possib…
Sampling-based proofs of almost-periodicity results and algorithmic applications
Eli Ben-Sasson, Noga Ron-Zewi, Madhur Tulsiani +1
We give new combinatorial proofs of known almost-periodicity results for sumsets of sets with small doubling in the spirit of Croot and Sisask, whose almost-periodicity lemma has h…
An additive combinatorics approach to the log-rank conjecture in communication complexity
Eli Ben-Sasson, Shachar Lovett, Noga Zewi
For a -valued matrix let denote the deterministic communication complexity of the boolean function associated with . The log-rank conjecture of Lovász…
Robust Locally Testable Codes and Products of Codes
Eli Ben-Sasson, Madhu Sudan
We continue the investigation of locally testable codes, i.e., error-correcting codes for whom membership of a given word in the code can be tested probabilistically by examining i…