Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > SUBLINEAR-TIME ALGORITHMS:
Reports tagged with Sublinear-time algorithms:
TR03-019 | 3rd April 2003
Eli Ben-Sasson, Oded Goldreich, Madhu Sudan

#### Bounds on 2-Query Codeword Testing.

Revisions: 1

We present upper bounds on the size of codes that are locally
testable by querying only two input symbols. For linear codes, we
show that any $2$-locally testable code with minimal distance
$\delta n$ over a finite field $F$ cannot have more than
$|F|^{3/\delta}$ codewords. This result holds even ... more >>>

TR04-013 | 10th February 2004
Oded Goldreich, Dana Ron

#### On Estimating the Average Degree of a Graph.

Following Feige, we consider the problem of
estimating the average degree of a graph.
Using neighbor queries'' as well as degree queries'',
we show that the average degree can be approximated
arbitrarily well in sublinear time, unless the graph is extremely sparse
(e.g., unless the graph has a sublinear ... more >>>

TR12-044 | 22nd April 2012
Swastik Kopparty

#### List-Decoding Multiplicity Codes

We study the list-decodability of multiplicity codes. These codes, which are based on evaluations of high-degree polynomials and their derivatives, have rate approaching $1$ while simultaneously allowing for sublinear-time error-correction. In this paper, we show that multiplicity codes also admit powerful list-decoding and local list-decoding algorithms correcting a large fraction ... more >>>

ISSN 1433-8092 | Imprint