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

__
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

__
TR21-090
| 14th June 2021
__

Divesh Aggarwal, Eldon Chung, Maciej Obremski, Joao Ribeiro#### On Secret Sharing, Randomness, and Random-less Reductions for Secret Sharing

__
TR19-173
| 28th November 2019
__

Divesh Aggarwal, Siyao Guo, Maciej Obremski, Joao Ribeiro, Noah Stephens-Davidowitz#### Extractor Lower Bounds, Revisited

Revisions: 1

Omar Alrabiah, Jesse Goodman, Jonathan Mosheiff, Joao Ribeiro

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 >>>

Huck Bennett, Mahdi Cheraghchi, Venkatesan Guruswami, Joao Ribeiro

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 >>>

Divesh Aggarwal, Eldon Chung, Maciej Obremski, Joao Ribeiro

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 >>>

Divesh Aggarwal, Siyao Guo, Maciej Obremski, Joao Ribeiro, Noah Stephens-Davidowitz

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 >>>