Results 2201 - 2210 of 23900

Over the past 10 years, there have been significant advances in our understanding of symmetric and structured error-correcting codes, particularly binary Reed-Muller (RM) codes. For simplicity, we refer to this line of inquiry as “capacity via symmetry”. While some early breakthroughs for erasure channels were based entirely on symmetry, extending these results to the binary symmetric channel (BSC) and other binary memoryless symmetric (BMS) channels has relied conditions such as nesting that provide multiple weakly correlated "looks" at a single code bit. In this talk, we summarize these advances and discuss some recent extensions (e.g., to classical-quantum channels). We conclude by discussing some interesting open problems and possibilities for the future.

The Learning Parity with Noise (LPN) problem underlies several classic cryptographic primitives. Researchers have endeavored to demonstrate the algorithmic difficulty of this problem by attempting to find a reduction from the decoding problem of linear codes, for which several hardness results exist. Earlier studies used code smoothing as a technical tool to achieve such reductions, showing that they are possible for codes with vanishing rate. This has left open the question of attaining a reduction with positive-rate codes. Addressing this case, we characterize the efficiency of the reduction in terms of the parameters of the decoding and LPN problems. As a conclusion, we isolate the parameter regimes for which a meaningful reduction is possible and the regimes for which its existence is unlikely.

Polynomial codes are algebraic error-correcting codes with widespread applications in TCS and allied areas. Due to their good rate vs distance tradeoff, as well as amenability to a plethora of algebraic techniques, an important line of enquiry is to understand their decodability properties under different paradigms.

Some of the best explicit polynomial code constructions have been achieved via a folding trick, realized in multiple ways, one of which is by using the classical derivative operator on polynomials. This opens an avenue for instantiating the polynomial method 'extended with multiplicities' in the analysis of such codes. In some cases, a successful a analysis might necessarily be sensitive to the characteristic of the underlying field.

In this talk, we will introduce an alternate, equally classical notion of derivative into the polynomial method, and see that this allows for characteristic insensitive constructions. We will see applications towards both efficient list decoding, and hardness of decoding.

This talk continues the discussion of interactive oracle proofs (IOPs), an interactive generalization of probabilistically-checkable proofs (PCPs). Such proofs offer extreme efficiency (theoretically and concretely), e.g., linear-time provers and polylogarithmic-time verifiers. To turn them into a cryptographic proof (i.e., a succinct argument), one additionally requires a polynomial commitment scheme, which allows for a prover to provide a short commitment to a polynomial P, and later can efficiently prove statements of the form “P(x)=y”.

In this work, we build on the code-switching technique of Ron-Zewi and Rothblum to construct multilinear polynomial commitment schemes (MLPCSs) over characteristic-2 fields, where the prover’s running time is inherited from the encoding time of the underlying error-correcting code. Crucially, we can employ codes without any “algebraic/multiplicative” properties, for which we only have error-correcting codes encodable in quasi-linear time. Our technique can be viewed as application of code interleaving.

To instantiate this construction, we utilize so-called Repeat-Accumulate-Accumulate codes, which are a simple class of turbo codes offering extremely efficient encoding and near-GV bound minimum distance. We will spend a good portion of this presentation describing these codes, discussing the challenges which arise in their analysis, and surveying some open problems.

Based on joint work Martijn Brehm, Binyi Chen, Ben Fisch, Ron D. Rothblum and Hadas Zeilberger.
Preprint: https://eprint.iacr.org/2024/1609.pdf

In this talk we will discuss the bias of random multivariate low-degree polynomials over F_2. Previous work has shown that random low-degree polynomials are, with high probability, unbiased on a uniformly random input.

We will consider more general notions of "bias" for low-degree polynomials. In particular, we will see that most low-degree polynomials are good extractors for all sufficiently small families of sources, and also for sumset sources, which are the most general large family of sources we know.

These results imply new complexity separations for linear ROBPs. The two main tools we use are a new structural result on sumset-punctured Reed-Muller codes, paired with a novel type of reduction between extractors. Using the new structural result, we obtain new limits on the power of sumset extractors, strengthening and generalizing the impossibility results of Chattopadhyay, Goodman, and Gurumukhani (ITCS 2024).

This talk is based on joint work with Omar Alrabiah, Jesse Goodman, and Jonathan Mosheiff.

I will present an exponential lower bound for the codeword length of 2-query relaxed locally decodable codes (RLDCs).  Combined with the almost linear constructions shown by Ben-Sasson, Goldreich, Harsha, Sudan, and Vadhan (SICOMP 2006) for some large but constant number of queries, this implies a sharp transition in the codeword length from super-exponential to polynomial, for some constant query complexity. In search for this threshold, I will further mention recent results for 3-query RLDCs and beyond.

Based on joint works with Alex Block, Jeremiah Blocki, Kuan Cheng,  Xin Li, Yu Zheng, and Minshen Zhu, and with Vinayak Kumar, Peter Manohar, and Geoffrey Mon.

Interactive oracle proofs (IOPs) extend the classical notion of probabilistically-checkable proofs (PCPs) by allowing a verifier to interact with a prover over a small number of rounds, while querying the prover’s messages in only a few locations.

A recent line of work gave highly-efficient IOPs outperforming state-of-the-art PCPs, for example, constant-round and constant-query IOPs with only a linear (and even approaching the witness length) amount of communication, as well as IOPs with linear-time prover complexity. These constructions were leveraged in turn to obtain highly-efficient succinct arguments and zero-knowledge proofs.

The improved efficiency was obtained by replacing polynomial-based codes, commonly used in such proof systems, with more efficient (tensor-based) codes. In particular, these constructions bypassed a barrier imposed by the need to encode the computation using a multiplication code.

In the talk I will survey these highly-efficient IOP constructions, and highlight some interesting open problems about error-correcting codes raised by these works.

Based on Joint works with Ron Rothblum and Mor Weiss.