Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > REED-MULLER CODE:
Reports tagged with Reed-Muller code:
TR02-020 | 13th March 2002
Elizaveta Okol'nishnikova

#### On one lower bound for branching programs

The method of obtaining lower bounds on the complexity
of Boolean functions for nondeterministic branching programs
is proposed.
A nonlinear lower bound on the complexity of characteristic
functions of Reed--Muller codes for nondeterministic
branching programs is obtained.

more >>>

TR13-175 | 6th December 2013
Venkatesan Guruswami, Chaoping Xing

#### Hitting Sets for Low-Degree Polynomials with Optimal Density

Revisions: 1

We give a length-efficient puncturing of Reed-Muller codes which preserves its distance properties. Formally, for the Reed-Muller code encoding $n$-variate degree-$d$ polynomials over ${\mathbb F}_q$ with $q \ge \Omega(d/\delta)$, we present an explicit (multi)-set $S \subseteq {\mathbb F}_q^n$ of size $N=\mathrm{poly}(n^d/\delta)$ such that every nonzero polynomial vanishes on at most ... more >>>

TR15-158 | 27th September 2015
Ofer Grossman, Dana Moshkovitz

#### Amplification and Derandomization Without Slowdown

We present techniques for decreasing the error probability of randomized algorithms and for converting randomized algorithms to deterministic (non-uniform) algorithms. Unlike most existing techniques that involve repetition of the randomized algorithm, and hence a slowdown, our techniques produce algorithms with a similar run-time to the original randomized algorithms.

The ... more >>>

TR20-142 | 15th September 2020

#### Relaxed Locally Correctable Codes with Improved Parameters

Locally decodable codes (LDCs) are error-correcting codes $C : \Sigma^k \to \Sigma^n$ that admit a local decoding algorithm that recovers each individual bit of the message by querying only a few bits from a noisy codeword. An important question in this line of research is to understand the optimal trade-off ... more >>>

TR21-118 | 11th August 2021
Daniel Augot, Sarah Bordage, Jade Nardi

#### Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes

Revisions: 1

We consider the proximity testing problem for error-correcting codes which consist in evaluations of multivariate polynomials either of bounded individual degree or bounded total degree. Namely, given an
oracle function $f : L^m \rightarrow \mathbb F_q$, where $L\subset \mathbb F_q$, a verifier distinguishes whether $f$ is the evaluation of a ... more >>>

ISSN 1433-8092 | Imprint