Skip to main content

5 Result(s)

within Noga Ron-Zewi Remove this filter English Remove this filter

and

  1. No Access

    Article

    Sparse affine-invariant linear codes are locally testable

    We show that sparse affine-invariant linear properties over arbitrary finite fields are locally testable with a constant number of queries. Given a finite field

    Eli Ben-Sasson, Noga Ron-Zewi, Madhu Sudan in computational complexity (2017)

  2. Chapter and Conference Paper

    On Public Key Encryption from Noisy Codewords

    Several well-known public key encryption schemes, including those of Alekhnovich (FOCS 2003), Regev (STOC 2005), and Gentry, Peikert and Vaikuntanathan (STOC 2008), rely on the conjectured intractability of in...

    Eli Ben-Sasson, Iddo Ben-Tov, Ivan Damgård… in Public-Key Cryptography – PKC 2016 (2016)

    Download PDF (410 KB) View Chapter

  3. No Access

    Chapter and Conference Paper

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

    We give new and simple combinatorial proofs of almost-periodicity results for sumsets of sets with small doubling in the spirit of Croot and Sisask [7], whose almost-periodicity lemma has had far-reaching implica...

    Eli Ben-Sasson, Noga Ron-Zewi, Madhur Tulsiani… in Automata, Languages, and Programming (2014)

  4. No Access

    Chapter and Conference Paper

    Absolutely Sound Testing of Lifted Codes

    In this work we present a strong analysis of the testability of a broad, and to date the most interesting known, class of “affine-invariant” codes. Affine-invariant codes are codes whose coordinates are associ...

    Elad Haramaty, Noga Ron-Zewi, Madhu Sudan in Approximation, Randomization, and Combinat… (2013)

  5. No Access

    Chapter and Conference Paper

    A New Upper Bound on the Query Complexity for Testing Generalized Reed-Muller codes

    Over a finite field \({\mathbb{F}}_q\) the (n,d,q)-Reed-Muller code is the code given by evaluations of n-variate polyn...

    Noga Ron-Zewi, Madhu Sudan in Approximation, Randomization, and Combinat… (2012)