Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > JOAO RIBEIRO:
All reports by Author Joao Ribeiro:

TR24-093 | 16th May 2024
Omar Alrabiah, Jesse Goodman, Jonathan Mosheiff, Joao Ribeiro

Low-Degree Polynomials Are Good Extractors

We prove that random low-degree polynomials (over $\mathbb{F}_2$) are unbiased, in an extremely general sense. That is, we show that random low-degree polynomials are good randomness extractors for a wide class of distributions. Prior to our work, such results were only known for the small families of (1) uniform sources, ... more >>>


TR22-156 | 15th November 2022
Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami, Joao Ribeiro

Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all $\ell_p$ Norms

Revisions: 2

We prove that the Minimum Distance Problem (MDP) on linear codes over any fixed finite field and parameterized by the input distance bound is W[1]-hard to approximate within any constant factor. We also prove analogous results for the parameterized Shortest Vector Problem (SVP) on integer lattices. Specifically, we prove that ... more >>>


TR21-090 | 14th June 2021
Divesh Aggarwal, Eldon Chung, Maciej Obremski, Joao Ribeiro

On Secret Sharing, Randomness, and Random-less Reductions for Secret Sharing

Secret-sharing is one of the most basic and oldest primitives in cryptography, introduced by Shamir and Blakely in the 70s. It allows to strike a meaningful balance between availability and confidentiality of secret information. It has a host of applications most notably in threshold cryptography and multi-party computation. All known ... more >>>


TR19-173 | 28th November 2019
Divesh Aggarwal, Siyao Guo, Maciej Obremski, Joao Ribeiro, Noah Stephens-Davidowitz

Extractor Lower Bounds, Revisited

Revisions: 1

We revisit the fundamental problem of determining seed length lower bounds for strong extractors and natural variants thereof. These variants stem from a ``change in quantifiers'' over the seeds of the extractor: While a strong extractor requires that the average output bias (over all seeds) is small for all input ... more >>>




ISSN 1433-8092 | Imprint