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

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

TR19-063 | 28th April 2019
Vikraman Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay

#### Efficient Black-Box Identity Testing for Free Group Algebra

Hrubeš and Wigderson [HW14] initiated the study of
noncommutative arithmetic circuits with division computing a
noncommutative rational function in the free skew field, and
raised the question of rational identity testing. It is now known
that the problem can be solved in deterministic polynomial time in
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 >>> TR20-025 | 20th February 2020 Chetan Gupta, Vimal Raj Sharma, Raghunath Tewari #### Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs We show that given an embedding of an O(log n) genus bipartite graph, one can construct an edge weight function in logarithmic space, with respect to which the minimum weight perfect matching in the graph is unique, if one exists. As a consequence, we obtain that deciding whether the ... more >>> TR20-169 | 11th November 2020 Zeyu Guo, Noga Ron-Zewi #### Efficient List-Decoding with Constant Alphabet and List Sizes Revisions: 1 We present an explicit and efficient algebraic construction of capacity-achieving list decodable codes with both constant alphabet and constant list sizes. More specifically, for any$R \in (0,1)$and$\epsilon>0$, we give an algebraic construction of an infinite family of error-correcting codes of rate$R$, over an alphabet of size ... more >>> TR15-116 | 21st July 2015 Joshua Brakensiek, Venkatesan Guruswami, Samuel Zbarsky #### Efficient Low-Redundancy Codes for Correcting Multiple Deletions Revisions: 1 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 >>> TR21-118 | 11th August 2021 Daniel Augot, Sarah Bordage, Jade Nardi #### Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes We consider the proximity testing problem for error-correcting codes which consist in evaluations of multivariate polynomials either of bounded individual degree or bounded total degree. Namely, given an oracle function$f : L^m \rightarrow \mathbb F_q$, where$L\subset \mathbb F_q$, a verifier distinguishes whether$f$is the evaluation of a ... 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 >>> TR20-125 | 17th August 2020 Gaurav Sinha #### Efficient reconstruction of depth three circuits with top fan-in two Revisions: 2 In this paper we develop efficient randomized algorithms to solve the black-box reconstruction problem for polynomials(over finite fields) computable by depth three arithmetic circuits with alternating addition/multiplication gates, such that top(output) gate is an addition gate with in-degree$2$. Such circuits naturally compute polynomials of the form$G\times(T_1 + T_2)$, ... 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 >>> TR19-008 | 20th January 2019 Ashish Dwivedi, Rajat Mittal, Nitin Saxena #### Efficiently factoring polynomials modulo$p^4$Polynomial factoring has famous practical algorithms over fields-- finite, rational \&$p$-adic. However, modulo prime powers it gets hard as there is non-unique factorization and a combinatorial blowup ensues. For example,$x^2+p \bmod p^2$is irreducible, but$x^2+px \bmod p^2$has exponentially many factors! We present the first randomized poly($\deg ... 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 >>>

TR20-088 | 9th June 2020
Bill Fefferman, Zachary Remscrim

#### Eliminating Intermediate Measurements in Space-Bounded Quantum Computation

A foundational result in the theory of quantum computation known as the principle of safe storage'' shows that it is always possible to take a quantum circuit and produce an equivalent circuit that makes all measurements at the end of the computation. While this procedure is time efficient, meaning that ... more >>>

TR21-087 | 22nd June 2021
Uma Girish, Ran Raz

#### Eliminating Intermediate Measurements using Pseudorandom Generators

Revisions: 1

We show that quantum algorithms of time T and space $S \ge \log T$ with intermediate measurements can be simulated by quantum algorithms of time $T\cdot \mathrm{poly}(S)$ and space $O(S\cdot \log T)$ without intermediate measurements. The best simulations prior to this work required either $\Omega(T)$ space (by the deferred measurement ... more >>>

TR21-103 | 18th July 2021
Eli Ben-Sasson, Dan Carmon, Swastik Kopparty, David Levit

#### Elliptic Curve Fast Fourier Transform (ECFFT) Part I: Fast Polynomial Algorithms over all Finite Fields

Revisions: 1

Over finite fields $F_q$ containing a root of unity of smooth order $n$ (smoothness means $n$ is the product of small primes), the Fast Fourier Transform (FFT) leads to the fastest known algebraic algorithms for many basic polynomial operations, such as multiplication, division, interpolation and multi-point evaluation. These operations can ... 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 >>>

TR21-054 | 14th April 2021
James Cook, Ian Mertz

#### Encodings and the Tree Evaluation Problem

We show that the Tree Evaluation Problem with alphabet size $k$ and height $h$ can be solved by branching programs of size $k^{O(h/\log h)} + 2^{O(h)}$. This answers a longstanding challenge of Cook et al. (2009) and gives the first general upper bound since the problem's inception.

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

TR18-206 | 3rd December 2018

#### Equality Alone Does Not Simulate Randomness

Revisions: 1

The canonical problem that gives an exponential separation between deterministic and randomized communication complexity in the classical two-party communication model is Equality'. In this work, we show that even allowing access to an Equality' oracle, deterministic protocols remain exponentially weaker than randomized ones. More precisely, we exhibit a total function ... 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 >>>

TR19-143 | 25th October 2019
Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian

#### Equivalence of Systematic Linear Data Structures and Matrix Rigidity

Recently, Dvir, Golovnev, and Weinstein have shown that sufficiently strong lower bounds for linear data structures would imply new bounds for rigid matrices. However, their result utilizes an algorithm that requires an $NP$ oracle, and hence, the rigid matrices are not explicit. In this work, we derive an equivalence between ... 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 >>>

TR20-190 | 29th November 2020
Amit Levi, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma

#### Erasure-Resilient Sublinear-Time Graph Algorithms

We investigate sublinear-time algorithms that take partially erased graphs represented by adjacency lists as input. Our algorithms make degree and neighbor queries to the input graph and work with a specified fraction of adversarial erasures in adjacency entries. We focus on two computational tasks: testing if a graph is connected ... more >>>

TR18-195 | 18th November 2018
Sofya Raskhodnikova, Noga Ron-Zewi, Nithin Varma

#### Erasures versus Errors in Local Decoding and Property Testing

Revisions: 1

We initiate the study of the role of erasures in local decoding and use our understanding to prove a separation between erasure-resilient and tolerant property testing. Local decoding in the presence of errors has been extensively studied, but has not been considered explicitly in the presence of erasures.

Motivated by ... 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 >>>

TR20-038 | 15th March 2020
Ofer Grossman, Justin Holmgren

#### Error Correcting Codes for Uncompressed Messages

Most types of messages we transmit (e.g., video, audio, images, text) are not fully compressed, since they do not have known efficient and information theoretically optimal compression algorithms. When transmitting such messages, standard error correcting codes fail to take advantage of the fact that messages are not fully compressed.

We ... more >>>

TR21-020 | 15th February 2021
Gil Cohen, Dean Doron, Oren Renard, Ori Sberlo, Amnon Ta-Shma

#### Error Reduction For Weighted PRGs Against Read Once Branching Programs

Weighted pseudorandom generators (WPRGs), introduced by Braverman, Cohen and Garg [BCG20], is a generalization of pseudorandom generators (PRGs) in which arbitrary real weights are considered rather than a probability mass. Braverman et al. constructed WPRGs against read once branching programs (ROBPs) with near-optimal dependence on the error parameter. Chattopadhyay 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 >>>

TR20-135 | 9th September 2020
Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Sayantan Sen

#### Estimation of Graph Isomorphism Distance in the Query World

Revisions: 2

The graph isomorphism distance between two graphs $G_u$ and $G_k$ is the fraction of entries in the adjacency matrix that has to be changed to make $G_u$ isomorphic to $G_k$. We study the problem of estimating, up to a constant additive factor, the graph isomorphism distance between two graphs in ... 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

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 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 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 >>> TR18-116 | 18th June 2018 Xue Chen, David Zuckerman #### Existence of Simple Extractors Revisions: 1 We show that a small subset of seeds of any strong extractor also gives a strong extractor with similar parameters when the number of output bits is a constant. Specifically, if$Ext: \{0,1\}^n \times \{0,1\}^t \to \{0,1\}^m$is a strong$(k,\epsilon)$-extractor, then for at least 99% of choices of$\tilde{O}(n ... 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 >>>

TR20-163 | 5th November 2020
Gil Cohen, Noam Peri, Amnon Ta-Shma

#### Expander Random Walks: A Fourier-Analytic Approach

In this work we ask the following basic question: assume the vertices of an expander graph are labelled by $0,1$. What "test" functions $f : \{ 0,1\}^t \to \{0,1\}$ cannot distinguish $t$ independent samples from those obtained by a random walk? The expander hitting property due to Ajtai, Komlos and ... more >>>

TR21-091 | 29th June 2021
Gil Cohen, Dor Minzer, Shir Peleg, Aaron Potechin, Amnon Ta-Shma

#### Expander Random Walks: The General Case and Limitations

Cohen, Peri and Ta-Shma (STOC'21) considered the following question: Assume the vertices of an expander graph are labelled by $\pm 1$. What "test" functions $f : \{\pm 1\}^t \to \{\pm1 \}$ can or cannot distinguish $t$ independent samples from those obtained by a random walk? [CPTS'21] considered only balanced labelling, ... more >>>

TR18-159 | 11th September 2018
Igor Carboni Oliveira, Rahul Santhanam, Roei Tell

#### Expander-Based Cryptography Meets Natural Proofs

Revisions: 1

We introduce new forms of attack on expander-based cryptography, and in particular on Goldreich's pseudorandom generator and one-way function. Our attacks exploit low circuit complexity of the underlying expander's neighbor function and/or of the local predicate. Our two key conceptual contributions are:

* The security of Goldreich's PRG and OWF ... 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 >>>

TR20-136 | 11th September 2020
Irit Dinur, Yuval Filmus, Prahladh Harsha, Madhur Tulsiani

#### Explicit and structured sum of squares lower bounds from high dimensional expanders

We construct an explicit family of 3XOR instances which is hard for Omega(sqrt(log n)) levels of the Sum-of-Squares hierarchy. In contrast to earlier constructions, which involve a random component, our systems can be constructed explicitly in deterministic polynomial time.
Our construction is based on the high-dimensional expanders devised by Lubotzky, ... more >>>

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

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

Revisions: 1

This paper makes progress on the problem of explicitly constructing a binary tree code with constant distance and constant alphabet size.

For every constant $\delta < 1$ we give an explicit binary tree code with distance $\delta$ and alphabet size $(\log{n})^{O(1)}$, where $n$ is the depth of the tree. This ... more >>>

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

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

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

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

TR21-148 | 3rd November 2021
Benjamin Diamond, Amir Yehudayoff

#### Explicit Exponential Lower Bounds for Exact Hyperplane Covers

We describe an explicit and simple subset of the discrete hypercube which cannot be exactly covered by fewer than exponentially many hyperplanes. The proof exploits a connection to communication complexity, and relies heavily on Razborov's lower bound for disjointness.

more >>>

TR20-106 | 15th July 2020
Eshan Chattopadhyay, Jesse Goodman

#### Explicit Extremal Designs and Applications to Extractors

Revisions: 5

An $(n,r,s)$-design, or $(n,r,s)$-partial Steiner system, is an $r$-uniform hypergraph over $n$ vertices with pairwise hyperedge intersections of size $0$, we extract from $(N,K,n,k)$-adversarial sources of locality $0$, where $K\geq N^\delta$ and $k\geq\text{polylog }n$. The previous best result (Chattopadhyay et al., STOC 2020) required $K\geq N^{1/2+o(1)}$. As a result, we ... more >>>

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

Revisions: 1

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: 5 We explicitly construct an extractor for two independent sources on$n$bits, each with min-entropy at least$\log^C n$for a large enough constant$C$. Our extractor outputs one bit and has error$n^{-\Omega(1)}$. The best previous extractor, by Bourgain [B2], required each source to have min-entropy$.499n$. A key ... more >>> 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 >>> TR20-047 | 16th April 2020 Ronen Shaltiel, Jad Silbak #### Explicit Uniquely Decodable Codes for Space Bounded Channels That Achieve List-Decoding Capacity Revisions: 2 We consider codes for space bounded channels. This is a model for communication under noise that was introduced by Guruswami and Smith (J. ACM 2016) and lies between the Shannon (random) and Hamming (adversarial) models. In this model, a channel is a space bounded procedure that reads the codeword in ... 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 >>> TR19-174 | 2nd December 2019 Susanna de Rezende, Jakob Nordström, Kilian Risse, Dmitry Sokolov #### Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs We show exponential lower bounds on resolution proof length for pigeonhole principle (PHP) formulas and perfect matching formulas over highly unbalanced, sparse expander graphs, thus answering the challenge to establish strong lower bounds in the regime between balanced constant-degree expanders as in [Ben-Sasson and Wigderson '01] and highly unbalanced, dense ... 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 >>> TR18-204 | 30th November 2018 Makrand Sinha, Ronald de Wolf #### Exponential Separation between Quantum Communication and Logarithm of Approximate Rank Comments: 1 Chattopadhyay, Mande and Sherif (ECCC 2018) recently exhibited a total Boolean function, the sink function, that has polynomial approximate rank and polynomial randomized communication complexity. This gives an exponential separation between randomized communication complexity and logarithm of the approximate rank, refuting the log-approximate-rank conjecture. We show that ... more >>> TR19-089 | 21st June 2019 Adam Bene Watts, Robin Kothari, Luke Schaeffer, Avishay Tal #### Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits Recently, Bravyi, Gosset, and König (Science, 2018) exhibited a search problem called the 2D Hidden Linear Function (2D HLF) problem that can be solved exactly by a constant-depth quantum circuit using bounded fan-in gates (or QNC^0 circuits), but cannot be solved by any constant-depth classical circuit using bounded fan-in AND, ... 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 >>>

TR22-002 | 11th December 2021
Sravanthi Chede, Anil Shukla

#### Extending Merge Resolution to a Family of Proof Systems

Merge Resolution (MRes [Beyersdorff et al. J. Autom. Reason.'2021]) is a recently introduced proof system for false QBFs. Unlike other known QBF proof systems, it builds winning strategies for the universal player within the proofs. Every line of this proof system consists of existential clauses along with countermodels. MRes stores ... 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

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, N. V. Vinodchandran, 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 >>>

TR19-173 | 28th November 2019
Divesh Aggarwal, Siyao Guo, Maciej Obremski, Joao Ribeiro, Noah Stephens-Davidowitz

#### Extractor Lower Bounds, Revisited

Revisions: 1

We revisit the fundamental problem of determining seed length lower bounds for strong extractors and natural variants thereof. These variants stem from a `change in quantifiers'' over the seeds of the extractor: While a strong extractor requires that the average output bias (over all seeds) is small for all input ... 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 >>>

TR19-184 | 13th December 2019
Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Xin Li

#### Extractors for Adversarial Sources via Extremal Hypergraphs

Randomness extraction is a fundamental problem that has been studied for over three decades. A well-studied setting assumes that one has access to multiple independent weak random sources, each with some entropy. However, this assumption is often unrealistic in practice. In real life, natural sources of randomness can produce samples ... 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 >>>

TR19-058 | 16th April 2019
Pavel Pudlak, Vojtech Rodl

#### Extractors for small zero-fixing sources

A random variable $X$ is an $(n,k)$-zero-fixing source if for some subset $V\subseteq[n]$, $X$ is the uniform distribution on the strings $\{0,1\}^n$ that are zero on every coordinate outside of $V$. An $\epsilon$-extractor for $(n,k)$-zero-fixing sources is a mapping $F:\{0,1\}^n\to\{0,1\}^m$, for some $m$, such that $F(X)$ is $\epsilon$-close in statistical ... more >>>

TR21-147 | 22nd October 2021
Eshan Chattopadhyay, Jyun-Jie Liao

#### Extractors for Sum of Two Sources

Revisions: 1

We consider the problem of extracting randomness from \textit{sumset sources}, a general class of weak sources introduced by Chattopadhyay and Li (STOC, 2016). An $(n,k,C)$-sumset source $\mathbf{X}$ is a distribution on $\{0,1\}^n$ of the form $\mathbf{X}_1 + \mathbf{X}_2 + \ldots + \mathbf{X}_C$, where $\mathbf{X}_i$'s are independent sources on $n$ bits ... 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 >>>

TR21-150 | 7th November 2021
Eldon Chung, Maciej Obremski, Divesh Aggarwal

#### Extractors: Low Entropy Requirements Colliding With Non-Malleability

The known constructions of negligible error (non-malleable) two-source extractors can be broadly classified in three categories:

(1) Constructions where one source has min-entropy rate about $1/2$, the other source can have small min-entropy rate, but the extractor doesn't guarantee non-malleability.
(2) Constructions where one source is uniform, and the other ... more >>>

TR21-158 | 12th November 2021
Noah Fleming, Toniann Pitassi, Robert Robere

#### Extremely Deep Proofs

Revisions: 1

We further the study of supercritical tradeoffs in proof and circuit complexity, which is a type of tradeoff between complexity parameters where restricting one complexity parameter forces another to exceed its worst-case upper bound. In particular, we prove a new family of supercritical tradeoffs between depth and size for Resolution, ... more >>>

ISSN 1433-8092 | Imprint