Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > EXPLICIT CONSTRUCTIONS:
Reports tagged with explicit constructions:
TR98-055 | 4th September 1998
Luca Trevisan

#### Constructions of Near-Optimal Extractors Using Pseudo-Random Generators

We introduce a new approach to construct extractors -- combinatorial
objects akin to expander graphs that have several applications.
Our approach is based on error correcting codes and on the Nisan-Wigderson
pseudorandom generator. An application of our approach yields a
construction that is simple to ... more >>>

TR06-126 | 2nd October 2006
Piotr Indyk

#### Uncertainty Principles, Extractors, and Explicit Embeddings of L2 into L1

We give an explicit construction of a constant-distortion embedding of an n-dimensional L_2 space into an n^{1+o(1)}-dimensional L_1 space.

more >>>

TR07-086 | 7th September 2007
Venkatesan Guruswami, James R. Lee, Alexander Razborov

#### Almost Euclidean subspaces of $\ell_1^N$ via expander codes

We give an explicit (in particular, deterministic polynomial time)
construction of subspaces $X \subseteq \R^N$ of dimension $(1-o(1))N$ such that for every $x \in X$,
$$(\log N)^{-O(\log\log\log N)} \sqrt{N}\, \|x\|_2 \leq \|x\|_1 \leq \sqrt{N}\, \|x\|_2.$$
If we are allowed to use $N^{1/\log\log N}\leq N^{o(1)}$ random bits
and ... more >>>

TR09-135 | 10th December 2009
Zeev Dvir, Avi Wigderson

#### Monotone expanders - constructions and applications

The main purpose of this work is to formally define monotone expanders and motivate their study with (known and new) connections to other graphs and to several computational and pseudorandomness problems. In particular we explain how monotone expanders of constant degree lead to:
(1) Constant degree dimension expanders in finite ... more >>>

TR10-037 | 8th March 2010
Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson

#### Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers, and Extractors

We present new explicit constructions of *deterministic* randomness extractors, dispersers and related objects. We say that a
distribution $X$ on binary strings of length $n$ is a
$\delta$-source if $X$ assigns probability at most $2^{-\delta n}$
to any string of length $n$. For every $\delta>0$ we construct the
following poly($n$)-time ... more >>>

TR12-095 | 23rd July 2012
Avraham Ben-Aroya, Igor Shinkar

#### A Note on Subspace Evasive Sets

A subspace-evasive set over a field ${\mathbb F}$ is a subset of ${\mathbb F}^n$ that has small intersection with any low-dimensional affine subspace of ${\mathbb F}^n$. Interest in subspace evasive sets began in the work of Pudlák and Rödl (Quaderni di Matematica 2004). More recently, Guruswami (CCC 2011) showed that ... more >>>

TR12-127 | 3rd October 2012

#### An Explicit VC-Theorem for Low-Degree Polynomials

Let $X \subseteq \mathbb{R}^{n}$ and let ${\mathcal C}$ be a class of functions mapping $\mathbb{R}^{n} \rightarrow \{-1,1\}.$ The famous VC-Theorem states that a random subset $S$ of $X$ of size $O(\frac{d}{\epsilon^{2}} \log \frac{d}{\epsilon})$, where $d$ is the VC-Dimension of ${\mathcal C}$, is (with constant probability) an $\epsilon$-approximation for ${\mathcal C}$ ... more >>>

TR13-170 | 2nd December 2013
Venkatesan Guruswami, Carol Wang

#### Explicit rank-metric codes list-decodable with optimal redundancy

We construct an explicit family of linear rank-metric codes over any field ${\mathbb F}_h$ that enables efficient list decoding up to a fraction $\rho$ of errors in the rank metric with a rate of $1-\rho-\epsilon$, for any desired $\rho \in (0,1)$ and $\epsilon > 0$. Previously, a Monte Carlo construction ... 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 >>>

TR14-160 | 27th November 2014
Gil Cohen, Igor Shinkar

An $(n,k)$-bit-fixing source is a distribution on $n$ bit strings, that is fixed on $n-k$ of the coordinates, and jointly uniform on the remaining $k$ bits. Explicit constructions of bit-fixing extractors by Gabizon, Raz and Shaltiel [SICOMP 2006] and Rao [CCC 2009], extract $(1-o(1)) \cdot k$ bits for $k = ... more >>> TR15-095 | 14th June 2015 Gil Cohen #### Two-Source Dispersers for Polylogarithmic Entropy and Improved Ramsey Graphs In his 1947 paper that inaugurated the probabilistic method, Erdös proved the existence of$2\log{n}$-Ramsey graphs on$n$vertices. Matching Erdös' result with a constructive proof is a central problem in combinatorics, that has gained a significant attention in the literature. The state of the art result was obtained in ... more >>> TR15-119 | 23rd July 2015 Eshan Chattopadhyay, David Zuckerman #### Explicit Two-Source Extractors and Resilient Functions Revisions: 5 We explicitly construct an extractor for two independent sources on$n$bits, each with min-entropy at least$\log^C n$for a large enough constant$C$. Our extractor outputs one bit and has error$n^{-\Omega(1)}$. The best previous extractor, by Bourgain [B2], required each source to have min-entropy$.499n$. A key ... more >>> TR15-183 | 16th November 2015 Gil Cohen #### Non-Malleable Extractors - New Tools and Improved Constructions A non-malleable extractor is a seeded extractor with a very strong guarantee - the output of a non-malleable extractor obtained using a typical seed is close to uniform even conditioned on the output obtained using any other seed. The first contribution of this paper consists of two new and improved ... more >>> TR16-014 | 3rd February 2016 Gil Cohen, Leonard Schulman #### Extractors for Near Logarithmic Min-Entropy The main contribution of this work is an explicit construction of extractors for near logarithmic min-entropy. For any$\delta > 0$we construct an extractor for$O(1/\delta)n$-bit sources with min-entropy$(\log{n})^{1+\delta}$. This is most interesting when$\delta$is set to a small constant, though the result also yields an ... more >>> TR16-030 | 7th March 2016 Gil Cohen #### Non-Malleable Extractors with Logarithmic Seeds We construct non-malleable extractors with seed length$d = O(\log{n}+\log^{3}(1/\epsilon))$for$n$-bit sources with min-entropy$k = \Omega(d)$, where$\epsilon$is the error guarantee. In particular, the seed length is logarithmic in$n$for$\epsilon> 2^{-(\log{n})^{1/3}}$. This improves upon existing constructions that either require super-logarithmic seed length even for constant ... more >>> TR16-052 | 7th April 2016 Gil Cohen #### Making the Most of Advice: New Correlation Breakers and Their Applications Revisions: 1 A typical obstacle one faces when constructing pseudorandom objects is undesired correlations between random variables. Identifying this obstacle and constructing certain types of "correlation breakers" was central for recent exciting advances in the construction of multi-source and non-malleable extractors. One instantiation of correlation breakers is correlation breakers with advice. These ... more >>> TR16-088 | 1st June 2016 Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma #### Explicit two-source extractors for near-logarithmic min-entropy We explicitly construct extractors for two independent$n$-bit sources of$(\log n)^{1+o(1)}$min-entropy. Previous constructions required either$\mathrm{polylog}(n)$min-entropy \cite{CZ15,Meka15} or five sources \cite{Cohen16}. Our result extends the breakthrough result of Chattopadhyay and Zuckerman \cite{CZ15} and uses the non-malleable extractor of Cohen \cite{Cohen16}. The main new ingredient in our construction ... more >>> TR16-106 | 15th July 2016 Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma #### Low-error two-source extractors for polynomial min-entropy Revisions: 1 We construct explicit two-source extractors for$n$bit sources, requiring$n^\alpha$min-entropy and having error$2^{-n^\beta}$, for some constants$0 < \alpha,\beta < 1$. Previously, constructions for exponentially small error required either min-entropy$0.49n$\cite{Bou05} or three sources \cite{Li15}. The construction combines somewhere-random condensers based on the Incidence Theorem \cite{Zuc06,Li11}, ... more >>> TR18-032 | 14th February 2018 Gil Cohen, Bernhard Haeupler, Leonard Schulman #### Explicit Binary Tree Codes with Polylogarithmic Size Alphabet Revisions: 1 This paper makes progress on the problem of explicitly constructing a binary tree code with constant distance and constant alphabet size. For every constant$\delta < 1$we give an explicit binary tree code with distance$\delta$and alphabet size$(\log{n})^{O(1)}$, where$n$is the depth of the tree. This ... more >>> TR18-065 | 8th April 2018 Avraham Ben-Aroya, Dean Doron, Amnon Ta-Shma #### Near-Optimal Strong Dispersers, Erasure List-Decodable Codes and Friends Revisions: 1 A code$\mathcal{C}$is$(1-\tau,L)$erasure list-decodable if for every codeword$w$, after erasing any$1-\tau$fraction of the symbols of$w$, the remaining$\tau$-fraction of its symbols have at most$L$possible completions into codewords of$\mathcal{C}$. Non-explicitly, there exist binary$(1-\tau,L)$erasure list-decodable codes having rate$O(\tau)$and ... more >>> TR18-066 | 8th April 2018 Avraham Ben-Aroya, Gil Cohen, Dean Doron, Amnon Ta-Shma #### Two-Source Condensers with Low Error and Small Entropy Gap via Entropy-Resilient Functions In their seminal work, Chattopadhyay and Zuckerman (STOC'16) constructed a two-source extractor with error$\varepsilon$for$n$-bit sources having min-entropy$poly\log(n/\varepsilon)$. Unfortunately, the construction running-time is$poly(n/\varepsilon)$, which means that with polynomial-time constructions, only polynomially-large errors are possible. Our main result is a$poly(n,\log(1/\varepsilon))$-time computable two-source condenser. For any$k ... more >>>

TR18-157 | 10th September 2018
Nutan Limaye, Karteek Sreenivasiah, Srikanth Srinivasan, Utkarsh Tripathi, S Venkitesh

#### The Coin Problem in Constant Depth: Sample Complexity and Parity gates

Revisions: 2

The $\delta$-Coin Problem is the computational problem of distinguishing between coins that are heads with probability $(1+\delta)/2$ or $(1-\delta)/2,$ where $\delta$ is a parameter that is going to $0$. We study the complexity of this problem in the model of constant-depth Boolean circuits and prove the following results.

1. Upper ... more >>>

TR18-183 | 5th November 2018
Dean Doron, Pooya Hatami, William Hoza

#### Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas

Revisions: 2

We give an explicit pseudorandom generator (PRG) for constant-depth read-once formulas over the basis $\{\wedge, \vee, \neg\}$ with unbounded fan-in. The seed length of our PRG is $\widetilde{O}(\log(n/\varepsilon))$. Previously, PRGs with near-optimal seed length were known only for the depth-2 case (Gopalan et al. FOCS '12). For a constant depth ... more >>>

TR19-047 | 2nd April 2019
Mrinal Kumar, Ben Lee Volk

#### Lower Bounds for Matrix Factorization

We study the problem of constructing explicit families of matrices which cannot be expressed as a product of a few sparse matrices. In addition to being a natural mathematical question on its own, this problem appears in various incarnations in computer science; the most significant being in the context of ... more >>>

TR19-149 | 4th November 2019
Dean Doron, Pooya Hatami, William Hoza

#### Log-Seed Pseudorandom Generators via Iterated Restrictions

There are only a few known general approaches for constructing explicit pseudorandom generators (PRGs). The iterated restrictions'' approach, pioneered by Ajtai and Wigderson [AW89], has provided PRGs with seed length $\mathrm{polylog} n$ or even $\tilde{O}(\log n)$ for several restricted models of computation. Can this approach ever achieve the optimal seed ... more >>>

TR19-153 | 6th November 2019
Venkatesan Guruswami, Bernhard Haeupler, Amirbehshad Shahrasbi

#### Optimally Resilient Codes for List-Decoding from Insertions and Deletions

Revisions: 1

We give a complete answer to the following basic question: What is the maximal fraction of deletions or insertions tolerable by $q$-ary list-decodable codes with non-vanishing information rate?''

This question has been open even for binary codes, including the restriction to the binary insertion-only setting, where the best known results ... more >>>

TR20-192 | 27th December 2020
Oded Goldreich, Avi Wigderson

#### Constructing Large Families of Pairwise Far Permutations: Good Permutation Codes Based on the Shuffle-Exchange Network

We consider the problem of efficiently constructing an as large as possible family of permutations such that each pair of permutations are far part (i.e., disagree on a constant fraction of their inputs).
Specifically, for every $n\in\N$, we present a collection of $N=N(n)=(n!)^{\Omega(1)}$ pairwise far apart permutations $\{\pi_i:[n]\to[n]\}_{i\in[N]}$ and ... more >>>

TR21-154 | 10th November 2021
Inbar Ben Yaacov, Gil Cohen, Tal Yankovitz

#### Explicit Binary Tree Codes with Sub-Logarithmic Size Alphabet

Since they were first introduced by Schulman (STOC 1993), the construction of tree codes remained an elusive open problem. The state-of-the-art construction by Cohen, Haeupler and Schulman (STOC 2018) has constant distance and $(\log n)^{e}$ colors for some constant $e > 1$ that depends on the distance, where $n$ is ... more >>>

TR22-048 | 4th April 2022
Hanlin Ren, Rahul Santhanam, Zhikun Wang

#### On the Range Avoidance Problem for Circuits

We consider the range avoidance problem (called Avoid): given the description of a circuit $C:\{0, 1\}^n \to \{0, 1\}^\ell$ (where $\ell > n$), find a string $y\in\{0, 1\}^\ell$ that is not in the range of $C$. This problem is complete for the class APEPP that corresponds to explicit constructions of ... more >>>

ISSN 1433-8092 | Imprint