Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > A-Z > E:
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

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

TR18-021 | 30th January 2018
Omri Ben-Eliezer, Eldar Fischer

#### Earthmover Resilience and Testing in Ordered Structures

One of the main challenges in property testing is to characterize those properties that are testable with a constant number of queries. For unordered structures such as graphs and hypergraphs this task has been mostly settled. However, for ordered structures such as strings, images, and ordered graphs, the characterization problem ... more >>>

TR18-080 | 6th March 2018
Moritz Gobbert

#### Edge Hop: A Framework to Show NP-Hardness of Combinatorial Games

The topic of this paper is a game on graphs called Edge Hop. The game's goal is to move a marked token from a specific starting node to a specific target node. Further, there are other tokens on some nodes which can be moved by the player under suitable conditions. ... 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

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

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

TR18-022 | 1st February 2018
Omer Reingold, Guy Rothblum, Ron Rothblum

#### Efficient Batch Verification for UP

Consider a setting in which a prover wants to convince a verifier of the correctness of k NP statements. For example, the prover wants to convince the verifier that k given integers N_1,...,N_k are all RSA moduli (i.e., products of equal length primes). Clearly this problem can be solved by ... 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
(PTF).
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 Diptarka Chakraborty, 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 , Comments: 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 >>> TR18-093 | 10th May 2018 Irit Dinur, Pasin Manurangsi #### ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network We study the 2-ary constraint satisfaction problems (2-CSPs), which can be stated as follows: given a constraint graph$G = (V, E)$, an alphabet set$\Sigma$and, for each edge$\{u, v\} \in E$, a constraint$C_{uv} \subseteq \Sigma \times \Sigma$, the goal is to find an assignment$\sigma: V ... 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 >>>

TR18-050 | 15th March 2018
Irit Dinur, Oded Goldreich, Tom Gur

#### Every set in P is strongly testable under a suitable encoding

We show that every set in $\cal P$ is strongly testable under a suitable encoding. By strongly testable'' we mean having a (proximity oblivious) tester that makes a constant number of queries and rejects with probability that is proportional to the distance of the tested object from the property. By ... more >>>

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

#### Evolvability

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

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

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

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

TR18-032 | 14th February 2018
Gil Cohen, Bernhard Haeupler, Leonard Schulman

#### Explicit Binary Tree Codes with Polylogarithmic Size Alphabet

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

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

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: 3 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 __________________ C 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

Revisions: 1

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.
\begin{enumerate}
\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

#### Extracting All the Randomness from a Weakly Random Source

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

Revisions: 1

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

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