Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with explicit construction:
TR05-155 | 10th December 2005
Amir Shpilka

Constructions of low-degree and error-correcting epsilon-biased sets

In this work we give two new constructions of $\epsilon$-biased
generators. Our first construction answers an open question of
Dodis and Smith, and our second construction
significantly extends a result of Mossel et al.
In particular we obtain the following results:

1. We construct a family of asymptotically good binary ... more >>>

TR09-121 | 22nd November 2009
Zohar Karnin, Yuval Rabani, Amir Shpilka

Explicit Dimension Reduction and Its Applications

We construct a small set of explicit linear transformations mapping $R^n$ to $R^{O(\log n)}$, such that the $L_2$ norm of
any vector in $R^n$ is distorted by at most $1\pm o(1)$ in at
least a fraction of $1 - o(1)$ of the transformations in the set.
Albeit the tradeoff between ... more >>>

TR12-050 | 25th April 2012
Avraham Ben-Aroya, Gil Cohen

Gradual Small-Bias Sample Spaces

Revisions: 3

A $(k,\epsilon)$-biased sample space is a distribution over $\{0,1\}^n$ that $\epsilon$-fools every nonempty linear test of size at most $k$. Since they were introduced by Naor and Naor [SIAM J. Computing, 1993], these sample spaces have become a central notion in theoretical computer science with a variety of applications.

When ... more >>>

TR12-158 | 14th November 2012
Aditya Bhaskara, Devendra Desai, Srikanth Srinivasan

Optimal Hitting Sets for Combinatorial Shapes

We consider the problem of constructing explicit Hitting sets for Combinatorial Shapes, a class of statistical tests first studied by Gopalan, Meka, Reingold, and Zuckerman (STOC 2011). These generalize many well-studied classes of tests, including symmetric functions and combinatorial rectangles. Generalizing results of Linial, Luby, Saks, and Zuckerman (Combinatorica 1997) ... more >>>

TR13-120 | 4th September 2013
Zeyu Guo

Randomness-efficient Curve Samplers

Curve samplers are sampling algorithms that proceed by viewing the domain as a vector space over a finite field, and randomly picking a low-degree curve in it as the sample. Curve samplers exhibit a nice property besides the sampling property: the restriction of low-degree polynomials over the domain to the ... more >>>

TR14-069 | 5th May 2014
Shashank Agrawal, Divya Gupta, Hemanta Maji, Omkant Pandey, Manoj Prabhakaran

Explicit Non-Malleable Codes Resistant to Permutations

The notion of non-malleable codes was introduced as a relaxation of standard error-correction and error-detection. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message, or a completely unrelated value.

In the information theoretic setting, although existence of such codes for various ... more >>>

TR15-116 | 21st July 2015
Joshua Brakensiek, Venkatesan Guruswami, Samuel Zbarsky

Efficient Low-Redundancy Codes for Correcting Multiple Deletions

We consider the problem of constructing binary codes to recover from $k$-bit deletions with efficient encoding/decoding, for a fixed $k$. The single deletion case is well understood, with the Varshamov-Tenengolts-Levenshtein code from 1965 giving an asymptotically optimal construction with $\approx 2^n/n$ codewords of length $n$, i.e., at most $\log n$ ... more >>>

TR15-117 | 21st July 2015
Boris Bukh, Venkatesan Guruswami

An improved bound on the fraction of correctable deletions

Revisions: 1

We consider codes over fixed alphabets against worst-case symbol deletions. For any fixed $k \ge 2$, we construct a family of codes over alphabet of size $k$ with positive rate, which allow efficient recovery from a worst-case deletion fraction approaching $1-\frac{2}{k+1}$. In particular, for binary codes, we are able to ... more >>>

TR15-178 | 10th November 2015
Eshan Chattopadhyay, Xin Li

Extractors for Sumset Sources

We propose a new model of weak random sources which we call sumset sources. A sumset source $\mathbf{X}$ is the sum of $C$ independent sources $\mathbf{X}_1,\ldots,\mathbf{X}_C$, where each $\mathbf{X}_i$ is an $n$-bit source with min-entropy $k$. We show that extractors for this class of sources can be used to give ... more >>>

TR16-196 | 5th December 2016
Igor Carboni Oliveira, Rahul Santhanam

Pseudodeterministic Constructions in Subexponential Time

We study {\it pseudodeterministic constructions}, i.e., randomized algorithms which output the {\it same solution} on most computation paths. We establish unconditionally that there is an infinite sequence $\{p_n\}_{n \in \mathbb{N}}$ of increasing primes and a randomized algorithm $A$ running in expected sub-exponential time such that for each $n$, on input ... more >>>

TR17-163 | 2nd November 2017
Michael Forbes, Amir Shpilka

A PSPACE Construction of a Hitting Set for the Closure of Small Algebraic Circuits

In this paper we study the complexity of constructing a hitting set for $\overline{VP}$, the class of polynomials that can be infinitesimally approximated by polynomials that are computed by polynomial sized algebraic circuits, over the real or complex numbers. Specifically, we show that there is a PSPACE algorithm that given ... more >>>

ISSN 1433-8092 | Imprint