Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z - Other

TR07-048 | 3rd April 2007
Alexandr Andoni, Piotr Indyk, Robert Krauthgamer

Earth Mover Distance over High-Dimensional Spaces

The Earth Mover Distance (EMD) between two equal-size sets
of points in R^d is defined to be the minimum cost of a
bipartite matching between the two pointsets. It is a natural metric
for comparing sets of features, and as such, it has received
significant interest in computer vision. Motivated ... more >>>

TR05-163 | 19th December 2005
Dvir Falik, Alex Samorodnitsky

Edge-isoperimetric inequalities and influences

We give a combinatorial proof of the result of Kahn, Kalai, and Linial, which states that every balanced boolean function on the n-dimensional boolean cube has a variable with influence of at least Omega(log(n)/n).The methods of the proof are then used to recover additional isoperimetric results for the cube, with ... more >>>

TR10-089 | 26th May 2010
Iftach Haitner, Omer Reingold, Salil Vadhan

Efficiency Improvements in Constructing Pseudorandom Generators from One-way Functions

We give a new construction of pseudorandom generators from any one-way function. The construction achieves better parameters and is simpler than that given in the seminal work of Haastad, Impagliazzo, Levin and Luby [SICOMP '99]. The key to our construction is a new notion of next-block pseudoentropy, which is inspired ... more >>>

TR07-094 | 3rd August 2007
Christian Glaßer, Heinz Schmitz, Victor Selivanov

Efficient Algorithms for Membership in Boolean Hierarchies of Regular Languages

The purpose of this paper is to provide efficient algorithms that decide membership for classes of several Boolean hierarchies for which efficiency (or even decidability) were previously not known. We develop new forbidden-chain characterizations for the single levels of these hierarchies and obtain the following results:

1. The classes of ... more >>>

TR06-033 | 2nd March 2006
Amit Agarwal, Elad Hazan

Efficient Algorithms for Online Game Playing and Universal Portfolio Management

A natural algorithmic scheme in online game playing is called `follow-the-leader', first proposed by Hannan in the 1950's. Simply stated, this method advocates the use of past history to make future predictions, by using the optimal strategy so far as the strategy for the next game iteration. Randomized variations on ... more >>>

TR01-053 | 17th July 2001
Piotr Berman, Marek Karpinski

Efficient Amplifiers and Bounded Degree Optimization

This paper studies the existence of efficient (small size)
amplifiers for proving explicit inaproximability results for bounded degree
and bounded occurrence combinatorial optimization problems, and gives
an explicit construction for such amplifiers. We use this construction
also later to improve the currently best known approximation lower bounds
more >>>

TR02-045 | 8th July 2002
Daniele Micciancio, Erez Petrank

Efficient and Concurrent Zero-Knowledge from any public coin HVZK protocol

We show how to efficiently transform any public coin honest verifier
zero knowledge proof system into a proof system that is concurrent
zero-knowledge with respect to any (possibly cheating) verifier via
black box simulation. By efficient we mean that our transformation
incurs only an additive overhead, ... more >>>

TR09-079 | 21st September 2009
Victor Chen, Elena Grigorescu, Ronald de Wolf

Efficient and Error-Correcting Data Structures for Membership and Polynomial Evaluation

Revisions: 1

We construct efficient data structures that are resilient against a constant fraction of adversarial noise. Our model requires that the decoder answers most queries correctly with high probability and for the remaining queries, the
decoder with high probability either answers correctly or declares ``don't know.'' Furthermore, if there is no ... more >>>

TR94-016 | 12th December 1994
Jin-Yi Cai, W. H. J. Fuchs, Dexter Kozen, Zicheng Liu

Efficient Average-Case Algorithms for the Modular Group

The modular group occupies a central position in many branches of
mathematical sciences. In this paper we give average polynomial-time
algorithms for the unbounded and bounded membership problems for
finitely generated subgroups of the modular group. The latter result
affirms a conjecture of Gurevich.

more >>>

TR05-158 | 12th December 2005
Chris Peikert, Alon Rosen

Efficient Collision-Resistant Hashing from Worst-Case Assumptions on Cyclic Lattices

The generalized knapsack function is defined as $f_{\a}(\x) = \sum_i
a_i \cdot x_i$, where $\a = (a_1, \ldots, a_m)$ consists of $m$
elements from some ring $R$, and $\x = (x_1, \ldots, x_m)$ consists
of $m$ coefficients from a specified subset $S \subseteq R$.
Micciancio ... more >>>

TR00-011 | 27th January 2000
Sotiris Nikoletseas, Paul Spirakis

Efficient Communication Establishment in Extremely Unreliable Large Networks

We consider here a large network of $n$ nodes which supports
only the following unreliable basic communication primitive:
when a node requests communication then this request
{\em may fail}, independently of other requests, with probability
$f<1$. Even if it succeeds, the request is answered by returning
a stable link to ... more >>>

TR10-083 | 13th May 2010
Mark Braverman, Anup Rao

Efficient Communication Using Partial Information

Revisions: 1

We show how to efficiently simulate the sending of a message M to a receiver who has partial information about the message, so that the expected number of bits communicated in the simulation is close to the amount of additional information that the message reveals to the receiver.

We ... more >>>

TR06-012 | 17th January 2006
Bruno Codenotti, Mauro Leoncini, Giovanni Resta

Efficient Computation of Nash Equilibria for Very Sparse Win-Lose Games

It is known that finding a Nash equilibrium for win-lose bimatrix
games, i.e., two-player games where the players' payoffs are zero
and one, is complete for the class PPAD.

We describe a linear time algorithm which computes a Nash
equilibrium for win-lose bimatrix games where the number of winning
positions ... more >>>

TR13-173 | 28th November 2013
Anindya De, Rocco Servedio

Efficient deterministic approximate counting for low degree polynomial threshold functions

We give a deterministic algorithm for
approximately counting satisfying assignments of a degree-$d$ polynomial threshold function
Given a degree-$d$ input polynomial $p(x_1,\dots,x_n)$ over $\mathbb{R}^n$
and a parameter $\epsilon > 0$, our algorithm approximates
\mathbf{P}_{x \sim \{-1,1\}^n}[p(x) \geq 0]
to within an additive $\pm \epsilon$ in time $O_{d,\epsilon}(1)\cdot ... more >>>

TR11-109 | 9th August 2011
Zvika Brakerski, Vinod Vaikuntanathan

Efficient Fully Homomorphic Encryption from (Standard) LWE

We present a fully homomorphic encryption scheme that is based solely on the (standard) learning with errors (LWE) assumption. Applying known results on LWE, the security of our scheme is based on the worst-case hardness of ``short vector problems'' on arbitrary lattices.

Our construction improves on previous works in two ... more >>>

TR17-074 | 29th April 2017
Vikraman Arvind, Rajit Datta, Partha Mukhopadhyay, Raja S

Efficient Identity Testing and Polynomial Factorization over Non-associative Free Rings

Revisions: 1

In this paper we study arithmetic computations over non-associative, and non-commutative free polynomials ring $\mathbb{F}\{x_1,x_2,\ldots,x_n\}$. Prior to this work, the non-associative arithmetic model of computation was considered by Hrubes, Wigderson, and Yehudayoff [HWY10]. They were interested in completeness and explicit lower bound results.

We focus on two main problems ... more >>>

TR15-047 | 2nd April 2015
Swastik Kopparty, Mrinal Kumar, Michael Saks

Efficient indexing of necklaces and irreducible polynomials over finite fields

We study the problem of indexing irreducible polynomials over finite fields, and give the first efficient algorithm for this problem. Specifically, we show the existence of poly(n, log q)-size circuits that compute a bijection between {1, ... , |S|} and the set S of all irreducible, monic, univariate polynomials of ... more >>>

TR12-043 | 16th April 2012
Zvika Brakerski, Yael Tauman Kalai

Efficient Interactive Coding Against Adversarial Noise

Revisions: 1

In this work, we study the fundamental problem of constructing interactive protocols that are robust to noise, a problem that was originally considered in the seminal works of Schulman (FOCS '92, STOC '93), and has recently regained popularity. Robust interactive communication is the interactive analogue of error correcting codes: Given ... 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 >>>

TR13-107 | 7th August 2013
Gil Cohen, Ivan Bjerre Damgard, Yuval Ishai, Jonas Kolker, Peter Bro Miltersen, Ran Raz, Ron Rothblum

Efficient Multiparty Protocols via Log-Depth Threshold Formulae

We put forward a new approach for the design of efficient multiparty protocols:

1. Design a protocol for a small number of parties (say, 3 or 4) which achieves
security against a single corrupted party. Such protocols are typically easy
to construct as they may employ techniques that do not ... more >>>

TR07-053 | 27th April 2007
Jens Groth, Amit Sahai

Efficient Non-interactive Proof Systems for Bilinear Groups

Non-interactive zero-knowledge proofs and non-interactive witness-indistinguishable proofs have played a significant role in the theory of cryptography. However, lack of efficiency has prevented them from being used in practice. One of the roots of this inefficiency is that non-interactive zero-knowledge proofs have been constructed for general NP-complete languages such as ... more >>>

TR11-073 | 3rd May 2011
Andrew Drucker

Efficient Probabilistically Checkable Debates

Probabilistically checkable debate systems (PCDSs) are debates between two competing provers, in which a polynomial-time verifier inspects a constant number of bits of the debate. It was shown by Condon, Feigenbaum, Lund, and Shor that every language in PSPACE has a PCDS in which the debate length is polynomially bounded. ... more >>>

TR10-155 | 14th October 2010
Brendan Juba, Madhu Sudan

Efficient Semantic Communication via Compatible Beliefs

In previous works, Juba and Sudan (STOC 2008) and Goldreich, Juba and Sudan (ECCC TR09-075) considered the idea of "semantic communication", wherein two players, a user and a server, attempt to communicate with each other without any prior common language (or communication protocol). They showed that if communication was goal-oriented ... more >>>

TR00-034 | 5th June 2000
Valentine Kabanets, Charles Rackoff, Stephen Cook

Efficiently Approximable Real-Valued Functions

We consider a class, denoted APP, of real-valued functions
f:{0,1}^n\rightarrow [0,1] such that f can be approximated, to
within any epsilon>0, by a probabilistic Turing machine running in
time poly(n,1/epsilon). We argue that APP can be viewed as a
generalization of BPP, and show that APP contains a natural
complete ... more >>>

TR11-042 | 25th March 2011
Ankur Moitra

Efficiently Coding for Interactive Communication

Revisions: 1

In 1992, Schulman proved a coding theorem for interactive communication and demonstrated that interactive communication protocols can be made robust to noise with only a constant slow-down (for a sufficiently small error rate) through a black-box reduction. However, this scheme is not computationally {\em efficient}: the running time to construct ... more >>>

TR06-029 | 21st February 2006
Deeparnab Chakrabarty, Nikhil R. Devanur, Vijay V. Vazirani

Eisenberg-Gale Markets: Rationality, Strongly Polynomial Solvability, and Competition Monotonicity

We study the structure of EG[2], the class of Eisenberg-Gale markets
with two agents. We prove that all markets in this class are rational and they
admit strongly polynomial algorithms whenever
the polytope containing the set of feasible utilities of the two agents can be described
via a combinatorial LP. ... more >>>

TR13-127 | 15th September 2013
Paul Beame, Raphael Clifford, Widad Machmouchi

Element Distinctness, Frequency Moments, and Sliding Windows

We derive new time-space tradeoff lower bounds and algorithms for exactly computing statistics of input data, including frequency moments, element distinctness, and order statistics, that are simple to calculate for sorted data. In particular, we develop a randomized algorithm for the element distinctness problem whose time $T$ and space $S$ ... more >>>

TR97-018 | 8th May 1997
Oded Goldreich, Shai Halevi

Eliminating Decryption Errors in the Ajtai-Dwork Cryptosystem.

Following Ajtai's lead, Ajtai and Dwork have recently introduced a
public-key encryption scheme which is secure under the assumption
that a certain computational problem on lattices is hard on the
worst-case. Their encryption method may cause decryption errors,
though with small probability (i.e., inversely proportional to the
more >>>

TR08-001 | 5th January 2008
Ran Raz

Elusive Functions and Lower Bounds for Arithmetic Circuits

A basic fact in linear algebra is that the image of the curve
$f(x)=(x^1,x^2,x^3,...,x^m)$, say over $C$, is not contained in any
$m-1$ dimensional affine subspace of $C^m$. In other words, the image
of $f$ is not contained in the image of any polynomial-mapping
$G:C^{m-1} ---> C^m$ ... more >>>

TR14-063 | 23rd April 2014
Adam Klivans, Pravesh Kothari

Embedding Hard Learning Problems into Gaussian Space

We give the first representation-independent hardness result for agnostically learning halfspaces with respect to the Gaussian distribution. We reduce from the problem of learning sparse parities with noise with respect to the uniform distribution on the hypercube (sparse LPN), a notoriously hard problem in computer science and show that ... more >>>

TR17-012 | 17th January 2017
Dominik Barth, Moritz Beck, Titus Dose, Christian Glaßer, Larissa Michler, Marc Technau

Emptiness Problems for Integer Circuits

We study the computational complexity of emptiness problems for circuits over sets of natural numbers with the operations union, intersection, complement, addition, and multiplication. For most settings of allowed operations we precisely characterize the complexity in terms of completeness for classes like NL, NP, and PSPACE. The case where intersection, ... more >>>

TR13-080 | 4th June 2013
Dmitry Gavinsky, Shachar Lovett

En Route to the log-rank Conjecture: New Reductions and Equivalent Formulations

We prove that several measures in communication complexity are equivalent, up to polynomial factors in the logarithm of the rank of the associated matrix: deterministic communication complexity, randomized communication complexity, information cost and zero-communication cost. This shows that in order to prove the log-rank conjecture, it suffices to show that ... more >>>

TR06-138 | 13th November 2006
Kei Uchizawa, Rodney Douglas

Energy Complexity and Entropy of Threshold Circuits

Circuits composed of threshold gates (McCulloch-Pitts neurons, or
perceptrons) are simplified models of neural circuits with the
advantage that they are theoretically more tractable than their
biological counterparts. However, when such threshold circuits are
designed to perform a specific computational task they usually
differ ... more >>>

TR11-159 | 27th November 2011
Oded Goldreich, Ron Rothblum

Enhancements of Trapdoor Permutations

Revisions: 1

We take a closer look at several enhancements of the notion of trapdoor permutations. Specifically, we consider the notions of enhanced trapdoor permutation (Goldreich 2004) and doubly enhanced trapdoor permutation (Goldreich 2008) as well as intermediate notions (Rothblum 2010). These enhancements arose in the study of Oblivious Transfer and NIZK, ... more >>>

TR08-019 | 6th March 2008
Stasys Jukna

Entropy of operators or why matrix multiplication is hard for small depth circuits

Revisions: 1

In this note we consider unbounded fanin depth-2 circuits with arbitrary boolean functions as gates.

We define the entropy of an operator f:{0,1}^n --> {0,1}^m is as the logarithm of the maximum number of vectors distinguishable by at least one special subfunction of f. Then we prove that every ... more >>>

TR14-112 | 23rd August 2014
Louay Bazzi

Entropy of weight distributions of small-bias spaces and pseudobinomiality

Revisions: 1

A classical bound in Information Theory asserts that small $L_1$-distance between probability distributions implies small difference in Shannon entropy, but the converse need not be true. We show that if a probability distribution on $\{0,1\}^n$ has small-bias, then the converse holds for its weight distribution in the proximity of the ... more >>>

TR01-018 | 23rd February 2001
Omer Reingold, Salil Vadhan, Avi Wigderson

Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors

The main contribution of this work is a new type of graph product, which we call the zig-zag
product. Taking a product of a large graph with a small graph, the resulting graph inherits
(roughly) its size from the large one, its degree from the small one, and ... more >>>

TR04-015 | 24th February 2004
Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan, Leen Torenvliet

Enumerations of the Kolmogorov Function

A recursive enumerator for a function $h$ is an algorithm $f$ which
enumerates for an input $x$ finitely many elements including $h(x)$.
$f$ is an $k(n)$-enumerator if for every input $x$ of length $n$, $h(x)$
is among the first $k(n)$ elements enumerated by $f$.
If there is a $k(n)$-enumerator for ... more >>>

TR07-136 | 28th November 2007
Felix Brandt, Felix Fischer, Markus Holzer

Equilibria of Graphical Games with Symmetries

We study graphical games where the payoff function of each player satisfies one of four types of symmetries in the actions of his neighbors. We establish that deciding the existence of a pure Nash equilibrium is NP-hard in graphical games with each of the four types of symmetry. Using a ... more >>>

TR10-010 | 16th January 2010
Shachar Lovett

Equivalence of polynomial conjectures in additive combinatorics

We study two conjectures in additive combinatorics. The first is the polynomial Freiman-Ruzsa conjecture, which relates to the structure of sets with small doubling. The second is the inverse Gowers conjecture for $U^ $, which relates to functions which locally look like quadratics. In both cases a weak form, with ... more >>>

TR14-001 | 4th January 2014
Swastik Kopparty, Shubhangi Saraf, Amir Shpilka

Equivalence of Polynomial Identity Testing and Deterministic Multivariate Polynomial Factorization

In this paper we show that the problem of deterministically factoring multivariate polynomials reduces to the problem of deterministic polynomial identity testing. Specifically, we show that given an arithmetic circuit (either explicitly or via black-box access) that computes a polynomial $f(X_1,\ldots,X_n)$, the task of computing arithmetic circuits for the factors ... more >>>

TR09-108 | 31st October 2009
Chongwon Cho, Chen-Kuei Lee, Rafail Ostrovsky

Equivalence of Uniform Key Agreement and Composition Insecurity

Revisions: 1

It is well known that proving the security of a key agreement protocol (even in a special case where the protocol transcript looks random to an outside observer) is at least as difficult as proving $P \not = NP$. Another (seemingly unrelated) statement in cryptography is the existence of two ... more >>>

TR11-081 | 15th May 2011
Vikraman Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar

Erdos-Renyi Sequences and Deterministic construction of Expanding Cayley Graphs

Given a finite group $G$ by its multiplication table as input, we give a deterministic polynomial-time construction of a directed Cayley graph on $G$ with $O(\log |G|)$ generators, which has a rapid mixing property and a constant spectral expansion.\\

We prove a similar result in the undirected case, and ... more >>>

TR01-001 | 31st December 2000
Jin-Yi Cai

Essentially every unimodular matrix defines an expander

We generalize the construction of Gabber and Galil
to essentially every unimodular matrix in $SL_2(\Z)$. It is shown that
every parabolic
or hyperbolic fractional linear transformation explicitly
defines an expander of bounded degree
and constant expansion. Thus all but a vanishingly small fraction
of unimodular matrices define expanders.

more >>>

TR13-087 | 4th June 2013
Hamed Hatami, Shachar Lovett

Estimating the distance from testable affine-invariant properties

Let $\cal{P}$ be an affine invariant property of functions $\mathbb{F}_p^n \to [R]$ for fixed $p$ and $R$. We show that if $\cal{P}$ is locally testable with a constant number of queries, then one can estimate the distance of a function $f$ from $\cal{P}$ with a constant number of queries. This ... more >>>

TR10-180 | 18th November 2010
Gregory Valiant, Paul Valiant

Estimating the unseen: A sublinear-sample canonical estimator of distributions

We introduce a new approach to characterizing the unobserved portion of a distribution, which provides sublinear-sample additive estimators for a class of properties that includes entropy and distribution support size. Together with the lower bounds proven in the companion paper [29], this settles the longstanding question of the sample complexities ... more >>>

TR15-074 | 29th April 2015
Mark Braverman, Young Kun Ko, Aviad Rubinstein, Omri Weinstein

ETH Hardness for Densest-$k$-Subgraph with Perfect Completeness

We show that, assuming the (deterministic) Exponential Time Hypothesis, distinguishing between a graph with an induced $k$-clique and a graph in which all $k$-subgraphs have density at most $1-\epsilon$, requires $n^{\tilde \Omega(log n)}$ time. Our result essentially matches the quasi-polynomial algorithms of Feige and Seltser [FS97] and Barman [Bar15] for ... more >>>

TR06-009 | 10th January 2006
Nutan Limaye, Meena Mahajan, Jayalal Sarma

Evaluating Monotone Circuits on Cylinders, Planes and Tori

We re-examine the complexity of evaluating monotone planar circuits
MPCVP, with special attention to circuits with cylindrical
embeddings. MPCVP is known to be in NC^3, and for the special
case of upward stratified circuits, it is known to be in
LogDCFL. We characterize cylindricality, which ... more >>>

TR13-140 | 8th October 2013
Atri Rudra, Mary Wootters

Every list-decodable code for high noise has abundant near-optimal rate puncturings

We show that any $q$-ary code with sufficiently good distance can be randomly punctured to obtain, with high probability, a code that is list decodable up to radius $1 - 1/q - \epsilon$ with near-optimal rate and list sizes.

Our results imply that ``most" Reed-Solomon codes are list decodable ... more >>>

TR12-184 | 26th December 2012
Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, Pooya Hatami, Shachar Lovett

Every locally characterized affine-invariant property is testable.

Revisions: 1

Let $\mathbb{F} = \mathbb{F}_p$ for any fixed prime $p \geq 2$. An affine-invariant property is a property of functions on $\mathbb{F}^n$ that is closed under taking affine transformations of the domain. We prove that all affine-invariant property having local characterizations are testable. In fact, we show a proximity-oblivious test for ... more >>>

TR08-010 | 17th January 2008
Itai Benjamini, Oded Schramm, Asaf Shapira

Every Minor-Closed Property of Sparse Graphs is Testable

Testing a property P of graphs in the bounded degree model deals with the following problem: given a graph G of bounded degree d we should distinguish (with probability 0.9, say) between the case that G satisfies P and the case that one should add/remove at least \epsilon d n ... more >>>

TR06-120 | 12th September 2006
Leslie G. Valiant


Living cells function according to complex mechanisms that operate in different ways depending on conditions. Evolutionary theory suggests that such mechanisms evolved as a result of a random search guided by selection and realized by genetic mutations. However, as some observers have noted, there has existed no theory that would ... more >>>

TR01-014 | 7th February 2001
Marcos Kiwi, Frederic Magniez, Miklos Santha

Exact and Approximate Testing/Correcting of Algebraic Functions: A Survey

In the late 80's Blum, Luby, Rubinfeld, Kannan et al. pioneered
the theory of self-testing as an alternative way of dealing with
the problem of software reliability.
Over the last decade this theory played a crucial role in
the construction of probabilistically checkable proofs and
the ... more >>>

TR16-139 | 8th September 2016
Ludwig Staiger

Exact constructive and computable dimensions

Revisions: 1

In this paper we derive several results which generalise the constructive
dimension of (sets of) infinite strings to the case of exact dimension. We
start with proving a martingale characterisation of exact Hausdorff
dimension. Then using semi-computable super-martingales we introduce the
notion of exact constructive dimension ... more >>>

TR11-074 | 27th April 2011
Ludwig Staiger

Exact constructive dimension

Revisions: 1

The present paper generalises results by Lutz and Ryabko. We prove a
martingale characterisation of exact Hausdorff dimension. On this base we
introduce the notion of exact constructive dimension of (sets of) infinite

Furthermore, we generalise Ryabko's result on the Hausdorff dimension of the
... more >>>

TR95-008 | 27th January 1995
Nader H. Bshouty

Exact Learning Boolean Functions via the Monotone Theory

TR07-049 | 1st June 2007
Beate Bollig, Niko Range, Ingo Wegener

Exact OBDD Bounds for some Fundamental Functions

Ordered binary decision diagrams (OBDDs) are nowadays the most common
dynamic data structure or representation type for Boolean functions.
Among the many areas of application are verification, model checking,
computer aided design, relational algebra, and symbolic graph algorithms.
Although many even exponential lower bounds on the OBDD size of Boolean ... more >>>

TR13-112 | 12th August 2013
Rohit Gurjar, Arpita Korwar, Jochen Messner, Thomas Thierauf

Exact Perfect Matching in Complete Graphs

A red-blue graph is a graph where every edge is colored either red or blue. The exact perfect matching problem asks for a perfect matching in a red-blue graph that has exactly a given number of red edges.

We show that for complete and bipartite complete graphs, the exact perfect ... more >>>

TR05-138 | 22nd November 2005
Peter Bürgisser, Felipe Cucker

Exotic quantifiers, complexity classes, and complete problems

We introduce some operators defining new complexity classes from existing ones in the Blum-Shub-Smale theory of computation over the reals. Each one of these operators is defined with the help of a quantifier differing from the usual ones, $\forall$ and $\exists$, and yet having a precise geometric meaning. Our agenda ... more >>>

TR16-144 | 15th September 2016
Sam Buss, Valentine Kabanets, Antonina Kolokolova, Michal Koucky

Expander Construction in VNC${}^1$

Revisions: 2

We give a combinatorial analysis (using edge expansion) of a variant of the iterative expander construction due to Reingold, Vadhan, and Wigderson [Annals of Mathematics, 2002], and show that this analysis can be formalized in the bounded-arithmetic system $VNC^1$ (corresponding to the ``$NC^1$ reasoning''). As a corollary, we prove the ... more >>>

TR05-079 | 25th July 2005
Stasys Jukna

Expanders and time-restricted branching programs

The \emph{replication number} of a branching program is the minimum
number R such that along every accepting computation at most R
variables are tested more than once. Hence 0\leq R\leq n for every
branching program in n variables. The best results so far were
exponential ... more >>>

TR11-140 | 31st October 2011
Vikraman Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar, Yadu Vasudev

Expanding Generator Sets for Solvable Permutation Groups

Revisions: 1

Let $G=\langle S\rangle$ be a solvable permutation group given as input by generating set $S$. I.e.\ $G$ is a solvable subgroup of the symmetric group $S_n$. We give a deterministic polynomial-time algorithm that computes an expanding generator set for $G$. More precisely, given a constant $\lambda <1$ we can compute ... more >>>

TR05-133 | 17th November 2005
Venkatesan Guruswami, Atri Rudra

Explicit Capacity-Achieving List-Decodable Codes

Revisions: 1

For every $0 < R < 1$ and $\eps > 0$, we present an explicit
construction of error-correcting codes of rate $R$ that can be list
decoded in polynomial time up to a fraction $(1-R-\eps)$ of errors.
These codes achieve the ``capacity'' for decoding from {\em ... 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 >>>

TR16-134 | 29th August 2016
Ronen Shaltiel, Jad Silbak

Explicit List-Decodable Codes with Optimal Rate for Computationally Bounded Channels

A stochastic code is a pair of encoding and decoding procedures $(Enc,Dec)$ where $Enc:\{0,1\}^k \times \{0,1\}^d \to \{0,1\}^n$, and a message $m \in \{0,1\}^k$ is encoded by $Enc(m,S)$ where $S \from \{0,1\}^d$ is chosen uniformly by the encoder. The code is $(p,L)$-list-decodable against a class $\mathcal{C}$ of ``channel functions'' $C:\{0,1\}^n ... more >>>

TR09-088 | 29th September 2009
Shachar Lovett, Yoav Tzur

Explicit lower bound for fooling polynomials by the sum of small-bias generators

Recently, Viola (CCC'08) showed that the sum of $d$ small-biased distributions fools degree-$d$ polynomial tests; that is, every polynomial expression of degree at most $d$ in the bits of the sum has distribution very close to that induced by this expression evaluated on uniformly selected random bits. We show that ... more >>>

TR13-104 | 20th July 2013
Parikshit Gopalan, Cheng Huang, Bob Jenkins, Sergey Yekhanin

Explicit Maximally Recoverable Codes with Locality

Consider a systematic linear code where some (local) parity symbols depend on few prescribed symbols, while other (heavy) parity symbols may depend on all data symbols. Local parities allow to quickly recover any single symbol when it is erased, while heavy parities provide tolerance to a large number of simultaneous ... more >>>

TR13-033 | 1st March 2013
Michael Forbes, Amir Shpilka

Explicit Noether Normalization for Simultaneous Conjugation via Polynomial Identity Testing

Revisions: 1

Mulmuley recently gave an explicit version of Noether's Normalization lemma for ring of invariants of matrices under simultaneous conjugation, under the conjecture that there are deterministic black-box algorithms for polynomial identity testing (PIT). He argued that this gives evidence that constructing such algorithms for PIT is beyond current techniques. In ... 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 >>>

TR16-036 | 13th March 2016
Eshan Chattopadhyay, Xin Li

Explicit Non-Malleable Extractors, Multi-Source Extractors and Almost Optimal Privacy Amplification Protocols

Revisions: 3

We make progress in the following three problems: 1. Constructing optimal seeded non-malleable extractors; 2. Constructing optimal privacy amplification protocols with an active adversary, for any possible security parameter; 3. Constructing extractors for independent weak random sources, when the min-entropy is extremely small (i.e., near logarithmic).

For the first ... more >>>

TR12-016 | 24th February 2012
Anindya De, Elchanan Mossel

Explicit Optimal hardness via Gaussian stability results

Revisions: 3

The results of Raghavendra (2008) show that assuming Khot's Unique Games Conjecture (2002), for every constraint satisfaction problem there exists a generic semi-definite program that achieves the optimal approximation factor. This result is existential as it does not provide an explicit optimal rounding procedure nor does it allow to calculate ... 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 >>>

TR12-117 | 17th September 2012
Loïck Magnin, Jérémie Roland

Explicit relation between all lower bound techniques for quantum query complexity

The polynomial method and the adversary method are the two main techniques to prove lower bounds on quantum query complexity, and they have so far been considered as unrelated approaches. Here, we show an explicit reduction from the polynomial method to the multiplicative adversary method. The proof goes by extending ... more >>>

TR15-144 | 1st September 2015
Raghu Meka

Explicit resilient functions matching Ajtai-Linial

Revisions: 1

A Boolean function on n variables is q-resilient if for any subset of at most q variables, the function is very likely to be determined by a uniformly random assignment to the remaining n-q variables; in other words, no coalition of at most q variables has significant influence on the ... more >>>

TR15-020 | 31st January 2015
Michael Viderman

Explicit Strong LTCs with inverse poly-log rate and constant soundness

Revisions: 1

An error-correcting code $C \subseteq \F^n$ is called $(q,\epsilon)$-strong locally testable code (LTC) if there exists a tester that makes at most $q$ queries to the input word. This tester accepts all codewords with probability 1 and rejects all non-codewords $x\notin C$ with probability at least $\epsilon \cdot \delta(x,C)$, where ... more >>>

TR13-060 | 10th April 2013
Venkatesan Guruswami, Swastik Kopparty

Explicit Subspace Designs

A subspace design is a collection $\{H_1,H_2,\dots,H_M\}$ of subspaces of ${\mathbf F}_q^m$ with the property that no low-dimensional subspace $W$ of ${\mathbf F}_q^m$ intersects too many subspaces of the collection. Subspace designs were introduced by Guruswami and Xing (STOC 2013) who used them to give a randomized construction of optimal ... more >>>

TR15-119 | 23rd July 2015
Eshan Chattopadhyay, David Zuckerman

Explicit Two-Source Extractors and Resilient Functions

Revisions: 2

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 >>>

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 >>>

TR17-041 | 6th March 2017
Amnon Ta-Shma

Explicit, almost optimal, epsilon-balanced codes

The question of finding an epsilon-biased set with close to optimal support size, or, equivalently, finding an explicit binary code with distance $\frac{1-\epsilon}{2}$ and rate close to the Gilbert-Varshamov bound, attracted a lot of attention in recent decades. In this paper we solve the problem almost optimally and show an ... more >>>

TR02-059 | 9th August 2002
Iordanis Kerenidis, Ronald de Wolf

Exponential Lower Bound for 2-Query Locally Decodable Codes

We prove exponential lower bounds on the length of 2-query
locally decodable codes. Goldreich et al. recently proved such bounds
for the special case of linear locally decodable codes.
Our proof shows that a 2-query locally decodable code can be decoded
with only 1 quantum query, and then ... more >>>

TR07-107 | 26th October 2007
Nathan Segerlind

Exponential lower bounds and integrality gaps for tree-like Lovasz-Schrijver procedures

The matrix cuts of Lov{\'{a}}sz and Schrijver are methods for tightening linear relaxations of zero-one programs by the addition of new linear inequalities. We address the question of how many new inequalities are necessary to approximate certain combinatorial problems with strong guarantees, and to solve certain instances of Boolean satisfiability.

... more >>>

TR16-064 | 19th April 2016
Stephen A. Cook, Toniann Pitassi, Robert Robere, Benjamin Rossman

Exponential Lower Bounds for Monotone Span Programs

Monotone span programs are a linear-algebraic model of computation which were introduced by Karchmer and Wigderson in 1993. They are known to be equivalent to linear secret sharing schemes, and have various applications in complexity theory and cryptography. Lower bounds for monotone span programs have been difficult to obtain because ... more >>>

TR13-018 | 29th January 2013
Luke Friedman, Yixin Xu

Exponential Lower Bounds for Refuting Random Formulas Using Ordered Binary Decision Diagrams

A propositional proof system based on ordered binary decision diagrams (OBDDs) was introduced by Atserias et al. Krajicek proved exponential lower bounds for a strong variant of this system using feasible interpolation, and Tveretina et al. proved exponential lower bounds for restricted versions of this system for refuting formulas derived ... more >>>

TR97-007 | 21st February 1997
Stasys Jukna

Exponential Lower Bounds for Semantic Resolution

In a semantic resolution proof we operate with clauses only
but allow {\em arbitrary} rules of inference:

C_1 C_2 ... C_m

Consistency is the only requirement. We prove a very simple
exponential lower bound for the size ... more >>>

TR04-041 | 18th May 2004
Michael Alekhnovich, Edward Hirsch, Dmitry Itsykson

Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas

DPLL (for Davis, Putnam, Logemann, and Loveland) algorithms form the largest family of contemporary algorithms for SAT (the propositional satisfiability problem) and are widely used in applications. The recursion trees of DPLL algorithm executions on unsatisfiable formulas are equivalent to tree-like resolution proofs. Therefore, lower bounds for tree-like resolution (which ... more >>>

TR13-110 | 12th August 2013
Xiaoming Sun, Marcos Villagra

Exponential Quantum-Classical Gaps in Multiparty Nondeterministic Communication Complexity

There are three different types of nondeterminism in quantum communication: i) $\nqp$-communication, ii) $\qma$-communication, and iii) $\qcma$-communication. In this \redout{paper} we show that multiparty $\nqp$-communication can be exponentially stronger than $\qcma$-communication. This also implies an exponential separation with respect to classical multiparty nondeterministic communication complexity. We argue that there exists ... more >>>

TR17-176 | 15th November 2017
Kamil Khadiev, Aliya Khadiev, Alexander Knop

Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies

In this paper, we study quantum OBDD model, it is a restricted version of read-once quantum branching programs, with respect to "width" complexity. It is known that the maximal gap between deterministic and quantum complexities is exponential. But there are few examples of functions with such a gap. We present ... more >>>

TR15-088 | 31st May 2015
Anat Ganor, Gillat Kol, Ran Raz

Exponential Separation of Communication and External Information

We show an exponential gap between communication complexity and external information complexity, by analyzing a communication task suggested as a candidate by Braverman [Bra13]. Previously, only a separation of communication complexity and internal information complexity was known [GKR14,GKR15].

More precisely, we obtain an explicit example of a search problem with ... more >>>

TR14-049 | 11th April 2014
Anat Ganor, Gillat Kol, Ran Raz

Exponential Separation of Information and Communication

Revisions: 1

We show an exponential gap between communication complexity and information complexity, by giving an explicit example for a communication task (relation), with information complexity $\leq O(k)$, and distributional communication complexity $\geq 2^k$. This shows that a communication protocol cannot always be compressed to its internal information. By a result of ... more >>>

TR14-113 | 27th August 2014
Anat Ganor, Gillat Kol, Ran Raz

Exponential Separation of Information and Communication for Boolean Functions

We show an exponential gap between communication complexity and information complexity for boolean functions, by giving an explicit example of a partial function with information complexity $\leq O(k)$, and distributional communication complexity $\geq 2^k$. This shows that a communication protocol for a partial boolean function cannot always be compressed to ... more >>>

TR07-074 | 7th August 2007
Dmitry Gavinsky, Pavel Pudlak

Exponential Separation of Quantum and Classical Non-Interactive Multi-Party Communication Complexity

We give the first exponential separation between quantum and
classical multi-party
communication complexity in the (non-interactive) one-way and
simultaneous message
passing settings.
For every k, we demonstrate a relational communication problem
between k parties
that can be solved exactly by a quantum simultaneous message passing
protocol of
cost ... more >>>

TR04-036 | 27th March 2004
Ziv Bar-Yossef, T.S. Jayram, Iordanis Kerenidis

Exponential Separation of Quantum and Classical One-Way Communication Complexity

We give the first exponential separation between quantum and bounded-error randomized one-way communication complexity. Specifically, we define the Hidden Matching Problem HM_n: Alice gets as input a string x in {0,1}^n and Bob gets a perfect matching M on the n coordinates. Bob's goal is to output a tuple (i,j,b) ... more >>>

TR06-086 | 25th July 2006
Dmitry Gavinsky, Julia Kempe, Ronald de Wolf

Exponential Separation of Quantum and Classical One-Way Communication Complexity for a Boolean Function

We give an exponential separation between one-way quantum and classical communication complexity for a Boolean function. Earlier such a separation was known only for a relation. A very similar result was obtained earlier but independently by Kerenidis and Raz [KR06]. Our version of the result gives an example in the ... more >>>

TR98-035 | 8th May 1998
Maria Luisa Bonet, Juan Luis Esteban, Jan Johannsen

Exponential Separations between Restricted Resolution and Cutting Planes Proof Systems

We prove an exponential lower bound for tree-like Cutting Planes
refutations of a set of clauses which has polynomial size resolution
refutations. This implies an exponential separation between tree-like
and dag-like proofs for both Cutting Planes and resolution; in both
cases only superpolynomial separations were known before.
In order to ... more >>>

TR13-072 | 3rd May 2013
Jan Johannsen

Exponential Separations in a Hierarchy of Clause Learning Proof Systems

Resolution trees with lemmas ($\mathrm{RTL}$) are a resolution-based propositional proof system that is related to the DPLL algorithm with clause learning. Its fragments $\mathrm{RTL}(k)$ are related to clause learning algorithms where the width of learned clauses is bounded by $k$.

For every $k$ up to $O(\log n)$, an exponential separation ... more >>>

TR10-078 | 27th April 2010
Holger Dell, Thore Husfeldt, Martin Wahlén

Exponential Time Complexity of the Permanent and the Tutte Polynomial

Revisions: 1

The Exponential Time Hypothesis (ETH) says that deciding the satisfiability of $n$-variable 3-CNF formulas requires time $\exp(\Omega(n))$. We relax this hypothesis by introducing its counting version #ETH, namely that every algorithm that counts the satisfying assignments requires time $\exp(\Omega(n))$. We transfer the sparsification lemma for $d$-CNF formulas to the counting ... more >>>

TR04-064 | 25th June 2004
Piotr Faliszewski

Exponential time reductions and sparse languages in NEXP

In this paper we define a many-one reduction which is allowed to work in exponential time but may only output polynomially many symbols. We show that there are no NEXP-hard sparse languages under our reduction unless EXP=UEXP.

more >>>

TR13-096 | 25th June 2013
Dana Ron, Rocco Servedio

Exponentially improved algorithms and lower bounds for testing signed majorities

A signed majority function is a linear threshold function $f : \{+1,1\}^n \to \{+1,1\}$ of the form
$f(x)={\rm sign}(\sum_{i=1}^n \sigma_i x_i)$ where each $\sigma_i \in \{+1,-1\}.$ Signed majority functions are a highly symmetrical subclass of the class of all linear threshold functions, which are functions of the form ${\rm ... more >>>

TR17-096 | 30th May 2017
Irit Dinur, Inbal Livni Navon

Exponentially Small Soundness for the Direct Product Z-test

Given a function $f:[N]^k\rightarrow[M]^k$, the Z-test is a three query test for checking if a function $f$ is a direct product, namely if there are functions $g_1,\dots g_k:[N]\to[M]$ such that $f(x_1,\ldots,x_k)=(g_1(x_1),\dots g_k(x_k))$ for every input $x\in [N]^k$.

This test was introduced by Impagliazzo et. al. (SICOMP 2012), who ... more >>>

TR17-063 | 10th April 2017
Benny Applebaum

Exponentially-Hard gap-CSP and local PRG via Local Hardcore Functions

The gap-ETH assumption (Dinur 2016; Manurangsi and Raghavendra 2016) asserts that it is exponentially-hard to distinguish between a satisfiable 3-CNF formula and a 3-CNF formula which is at most 0.99-satisfiable. We show that this assumption follows from the exponential hardness of finding a satisfying assignment for *smooth* 3-CNFs. Here smoothness ... more >>>

TR10-138 | 17th September 2010
Eric Allender, Luke Friedman, William Gasarch

Exposition of the Muchnik-Positselsky Construction of a Prefix Free Entropy Function that is not Complete under Truth-Table Reductions

In this paper we give an exposition of a theorem by Muchnik and Positselsky, showing that there is a universal prefix Turing machine U, with the property that there is no truth-table reduction from the halting problem to the set {(x,i) : there is a description d of length at ... more >>>

TR07-041 | 20th April 2007
Nicola Galesi, Massimo Lauria

Extending Polynomial Calculus to $k$-DNF Resolution

Revisions: 1

We introduce an algebraic proof system Pcrk, which combines together {\em Polynomial Calculus} (Pc) and {\em $k$-DNF Resolution} (Resk).
This is a natural generalization to Resk of the well-known {\em Polynomial Calculus with Resolution} (Pcr) system which combines together Pc and Resolution.

We study the complexity of proofs in such ... more >>>

TR16-070 | 24th April 2016
Mika Göös, Rahul Jain, Thomas Watson

Extension Complexity of Independent Set Polytopes

We exhibit an $n$-node graph whose independent set polytope requires extended formulations of size exponential in $\Omega(n/\log n)$. Previously, no explicit examples of $n$-dimensional $0/1$-polytopes were known with extension complexity larger than exponential in $\Theta(\sqrt{n})$. Our construction is inspired by a relatively little-known connection between extended formulations and (monotone) circuit ... more >>>

TR16-005 | 22nd January 2016
Olaf Beyersdorff, Leroy Chew, Mikolas Janota

Extension Variables in QBF Resolution

We investigate two QBF resolution systems that use extension variables: weak extended Q-resolution, where the extension variables are quantified at the innermost level, and extended Q-resolution, where the extension variables can be placed inside the quantifier prefix. These systems have been considered previously by Jussila et al. '07 who ... more >>>

TR09-004 | 15th January 2009
Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan

Extensions to the Method of Multiplicities, with applications to Kakeya Sets and Mergers

Revisions: 2

We extend the ``method of multiplicities'' to get the following results, of interest in combinatorics and randomness extraction.
\item We show that every Kakeya set in $\F_q^n$, the $n$-dimensional vector space over the finite field on $q$ elements, must be of size at least $q^n/2^n$. This bound is tight ... more >>>

TR99-046 | 17th November 1999
Ran Raz, Omer Reingold, Salil Vadhan

Extracting All the Randomness and Reducing the Error in Trevisan's Extractors

We give explicit constructions of extractors which work for a source of
any min-entropy on strings of length n. These extractors can extract any
constant fraction of the min-entropy using O(log^2 n) additional random
bits, and can extract all the min-entropy using O(log^3 n) additional
random bits. Both of these ... more >>>

TR98-047 | 21st August 1998
Salil Vadhan

Extracting All the Randomness from a Weakly Random Source

Revisions: 1 , Comments: 1

In this paper, we give explicit constructions of extractors which work for
a source of any min-entropy on strings of length $n$. The first
construction extracts any constant fraction of the min-entropy using
O(log^2 n) additional random bits. The second extracts all the
min-entropy using O(log^3 n) additional random ... more >>>

TR05-105 | 24th September 2005
Lance Fortnow, John Hitchcock, A. Pavan, Vinodchandran Variyam, Fengming Wang

Extracting Kolmogorov Complexity with Applications to Dimension Zero-One Laws

We apply recent results on extracting randomness from independent
sources to ``extract'' Kolmogorov complexity. For any $\alpha,
\epsilon > 0$, given a string $x$ with $K(x) > \alpha|x|$, we show
how to use a constant number of advice bits to efficiently
compute another string $y$, $|y|=\Omega(|x|)$, with $K(y) >
(1-\epsilon)|y|$. ... more >>>

TR00-059 | 11th August 2000
Omer Reingold, Ronen Shaltiel, Avi Wigderson

Extracting Randomness via Repeated Condensing

On an input probability distribution with some (min-)entropy
an {\em extractor} outputs a distribution with a (near) maximum
entropy rate (namely the uniform distribution).
A natural weakening of this concept is a condenser, whose
output distribution has a higher entropy rate than the
input distribution (without losing
much of ... more >>>

TR10-118 | 27th July 2010
Maurice Jansen

Extracting Roots of Arithmetic Circuits by Adapting Numerical Methods

Revisions: 2

For two polynomials $f \in \mathbb{F}[x_1, x_2, \ldots, x_n, y]$ and $p \in \mathbb{F}[x_1, x_2, \ldots, x_n]$, we say that $p$ is a root of $f$, if $f(x_1, x_2, \ldots, x_n, p) \equiv 0$. We study the relation between the arithmetic circuit sizes of $f$ and $p$ for general circuits ... more >>>

TR17-121 | 31st July 2017
Sumegha Garg, Ran Raz, Avishay Tal

Extractor-Based Time-Space Lower Bounds for Learning

A matrix $M: A \times X \rightarrow \{-1,1\}$ corresponds to the following learning problem: An unknown element $x \in X$ is chosen uniformly at random. A learner tries to learn $x$ from a stream of samples, $(a_1, b_1), (a_2, b_2) \ldots$, where for every $i$, $a_i \in A$ is chosen ... more >>>

TR06-134 | 18th October 2006
Venkatesan Guruswami, Chris Umans, Salil Vadhan

Extractors and condensers from univariate polynomials

Revisions: 1

We give new constructions of randomness extractors and lossless condensers that are optimal to within constant factors in both the seed length and the output length. For extractors, this matches the parameters of the current best known construction [LRVW03]; for lossless condensers, the previous best constructions achieved optimality to within ... more >>>

TR11-037 | 18th March 2011
Anindya De, Thomas Watson

Extractors and Lower Bounds for Locally Samplable Sources

Revisions: 3

We consider the problem of extracting randomness from sources that are efficiently samplable, in the sense that each output bit of the sampler only depends on some small number $d$ of the random input bits. As our main result, we construct a deterministic extractor that, given any $d$-local source with ... more >>>

TR00-009 | 21st February 2000
Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson

Extractors and pseudo-random generators with optimal seed length

We give the first construction of a pseudo-random generator with
optimal seed length that uses (essentially) arbitrary hardness.
It builds on the novel recursive use of the NW-generator in
a previous paper by the same authors, which produced many optimal
generators one of which was pseudo-random. This is achieved ... more >>>

TR07-056 | 10th July 2007
Zeev Dvir, Ariel Gabizon, Avi Wigderson

Extractors and Rank Extractors for Polynomial Sources

In this paper we construct explicit deterministic extractors from polynomial sources, namely from distributions sampled by low degree multivariate polynomials over finite fields. This naturally generalizes previous work on extraction from affine sources (which are degree 1 polynomials). A direct consequence is a deterministic extractor for distributions sampled by polynomial ... more >>>

TR13-025 | 6th February 2013
Xin Li

Extractors for a Constant Number of Independent Sources with Polylogarithmic Min-Entropy

Revisions: 1

We study the problem of constructing explicit extractors for independent general weak random sources. Given weak sources on $n$ bits, the probabilistic method shows that there exists a deterministic extractor for two independent sources with min-entropy as small as $\log n+O(1)$. However, even to extract from a constant number of ... more >>>

TR05-106 | 26th September 2005
Anup Rao

Extractors for a Constant Number of Polynomial Min-Entropy Independent Sources

Revisions: 1

We consider the problem of bit extraction from independent sources. We
construct an extractor that can extract from a constant number of
independent sources of length $n$, each of which have min-entropy
$n^\gamma$ for an arbitrarily small constant $\gamma > 0$. Our
constructions are different from recent extractor constructions
more >>>

TR15-121 | 25th July 2015
Xin Li

Extractors for Affine Sources with Polylogarithmic Entropy

We give the first explicit construction of deterministic extractors for affine sources over $F_2$, with entropy $k \geq \log^C n$ for some large enough constant $C$, where $n$ is the length of the source. Previously the best known results are by Bourgain \cite{Bourgain07}, Yehudayoff \cite{Yehudayoff10} and Li \cite{Li11a}, which require ... more >>>

TR11-056 | 14th April 2011
Emanuele Viola

Extractors for circuit sources

We obtain the first deterministic extractors for sources generated (or sampled) by small circuits of bounded depth. Our main results are:

(1) We extract $k (k/nd)^{O(1)}$ bits with exponentially small error from $n$-bit sources of min-entropy $k$ that are generated by functions $f : \{0,1\}^\ell \to \{0,1\}^n$ where each output ... more >>>

TR08-015 | 23rd January 2008
Anup Rao

Extractors for Low-Weight Affine Sources

We give polynomial time computable extractors for low-weight affine sources. A distribution is affine if it samples a random point from some unknown low dimensional subspace of F^n_2 . A distribution is low weight affine if the corresponding linear space has a basis of low-weight vectors. Low-weight ane sources are ... 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 >>>

TR11-129 | 22nd September 2011
Eli Ben-Sasson, Ariel Gabizon

Extractors for Polynomials Sources over Constant-Size Fields of Small Characteristic

Let $F$ be the field of $q$ elements, where $q=p^{\ell}$ for prime $p$. Informally speaking, a polynomial source is a distribution over $F^n$ sampled by low degree multivariate polynomials. In this paper, we construct extractors for polynomial sources over fields of constant size $q$ assuming $p \ll q$.

More generally, ... 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 >>>

TR12-047 | 24th April 2012
Emanuele Viola

Extractors for Turing-machine sources

We obtain the first deterministic randomness extractors
for $n$-bit sources with min-entropy $\ge n^{1-\alpha}$
generated (or sampled) by single-tape Turing machines
running in time $n^{2-16 \alpha}$, for all sufficiently
small $\alpha > 0$. We also show that such machines
cannot sample a uniform $n$-bit input to the Inner
Product function ... more >>>

TR01-036 | 2nd May 2001
Amnon Ta-Shma, David Zuckerman, Shmuel Safra

Extractors from Reed-Muller Codes

Finding explicit extractors is an important derandomization goal that has received a lot of attention in the past decade. This research has focused on two approaches, one related to hashing and the other to pseudorandom generators. A third view, regarding extractors as good error correcting codes, was noticed before. Yet, ... more >>>

TR04-099 | 11th November 2004
Ran Raz

Extractors with Weak Random Seeds

We show how to extract random bits from two or more independent
weak random sources, in cases where only one source is of linear
min-entropy and all other sources are of logarithmic min-entropy.
We also give improved constructions of mergers and condensers.
In all that comes below, $\delta$ is an ... more >>>

ISSN 1433-8092 | Imprint