Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > DERANDOMIZATION:
Reports tagged with derandomization:
TR95-061 | 27th November 1995
Alexander E. Andreev, Andrea E. F. Clementi, Jose' D. P. Rolim

Hitting sets derandomize BPP

Revisions: 1

We show that hitting sets can derandomize any BPP-algorithm.
This gives a positive answer to a fundamental open question in
probabilistic algorithms. More precisely, we present a polynomial
time deterministic algorithm which uses any given hitting set
to approximate the fractions of 1's in the ... more >>>


TR96-055 | 22nd October 1996
Alexander E. Andreev, Andrea E. F. Clementi, Jose' D. P. Rolim

Hitting Properties of Hard Boolean Operators and their Consequences on BPP

Revisions: 1 , Comments: 1

We present the first worst-case hardness conditions
on the circuit complexity of EXP functions which are
sufficient to obtain P=BPP. In particular, we show that
from such hardness conditions it is possible to construct
quick Hitting Sets Generators with logarithmic prize.
... more >>>


TR97-011 | 7th April 1997
Alexander E. Andreev, Andrea E. F. Clementi, Jose' D.P. Rolim and Trevisan

Weak Random Sources, Hitting Sets, and BPP Simulations

We show how to simulate any BPP algorithm in polynomial time
using a weak random source of min-entropy $r^{\gamma}$
for any $\gamma >0$.
This follows from a more general result about {\em sampling\/}
with weak random sources.
Our result matches an information-theoretic lower bound ... more >>>


TR98-023 | 16th April 1998
Eric Allender, Shiyu Zhou

Uniform Inclusions in Nondeterministic Logspace

We show that the complexity class LogFew is contained
in NL $\cap$ SPL. Previously, this was known only to
hold in the nonuniform setting.

more >>>

TR98-049 | 10th July 1998
Dimitris Fotakis, Paul Spirakis

Random Walks, Conditional Hitting Sets and Partial Derandomization

In this work we use random walks on expanders in order to
relax the properties of hitting sets required for partially
derandomizing one-side error algorithms. Building on a well-known
probability amplification technique [AKS87,CW89,IZ89], we use
random walks on expander graphs of subexponential (in the
random bit complexity) size so as ... more >>>


TR98-058 | 2nd August 1998
H. Buhrman, Dieter van Melkebeek, K.W. Regan, Martin Strauss, D. Sivakumar

A Generalization of Resource-Bounded Measure, With Application to the BPP vs. EXP Problem

We introduce "resource-bounded betting games", and propose
a generalization of Lutz's resource-bounded measure in which the choice
of next string to bet on is fully adaptive. Lutz's martingales are
equivalent to betting games constrained to bet on strings in lexicographic
order. We show that if strong pseudo-random number generators exist,
more >>>


TR98-074 | 16th December 1998
Madhu Sudan, Luca Trevisan, Salil Vadhan

Pseudorandom generators without the XOR Lemma

Revisions: 2


Impagliazzo and Wigderson have recently shown that
if there exists a decision problem solvable in time $2^{O(n)}$
and having circuit complexity $2^{\Omega(n)}$
(for all but finitely many $n$) then $\p=\bpp$. This result
is a culmination of a series of works showing
connections between the existence of hard predicates
and ... more >>>


TR99-004 | 3rd February 1999
Valentine Kabanets

Almost $k$-Wise Independence and Boolean Functions Hard for Read-Once Branching Programs

Revisions: 1

Andreev et al.~\cite{ABCR97} give constructions of Boolean
functions (computable by polynomial-size circuits) that require large
read-once branching program (1-b.p.'s): a function in P that requires
1-b.p. of size at least $2^{n-\polylog(n)}$, a function in quasipolynomial
time that requires 1-b.p. of size at least $2^{n-O(\log n)}$, and a
function in LINSPACE ... more >>>


TR99-045 | 16th November 1999
Valentine Kabanets, Jin-Yi Cai

Circuit Minimization Problem

We study the complexity of the circuit minimization problem:
given the truth table of a Boolean function f and a parameter s, decide
whether f can be realized by a Boolean circuit of size at most s. We argue
why this problem is unlikely to be in P (or ... more >>>


TR00-004 | 14th January 2000
Oded Goldreich, Salil Vadhan, Avi Wigderson

Simplified derandomization of BPP using a hitting set generator.


A hitting-set generator is a deterministic
algorithm which generates a set of strings that intersects
every dense set recognizable by a small circuit.
A polynomial time hitting-set generator readily implies $RP=P$.
Andreev \etal\/ (ICALP'96, and JACM 1998)
showed that if polynomial-time hitting-set
generator in fact implies ... 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 >>>


TR00-043 | 21st June 2000
Uriel Feige, Marek Karpinski, Michael Langberg

A Note on Approximating MAX-BISECTION on Regular Graphs


We design a $0.795$ approximation algorithm for the Max-Bisection problem
restricted to regular graphs. In the case of three regular graphs our
results imply an approximation ratio of $0.834$.

more >>>

TR00-056 | 20th July 2000
Oded Goldreich, Avi Wigderson

On Pseudorandomness with respect to Deterministic Observers.

In the theory of pseudorandomness, potential (uniform) observers
are modeled as probabilistic polynomial-time machines.
In fact many of the central results in
that theory are proven via probabilistic polynomial-time reductions.
In this paper we show that analogous deterministic reductions
are unlikely to hold. We conclude that randomness ... more >>>


TR01-012 | 4th January 2001
Evgeny Dantsin, Edward Hirsch, Sergei Ivanov, Maxim Vsemirnov

Algorithms for SAT and Upper Bounds on Their Complexity

We survey recent algorithms for the propositional
satisfiability problem, in particular algorithms
that have the best current worst-case upper bounds
on their complexity. We also discuss some related
issues: the derandomization of the algorithm of
Paturi, Pudlak, Saks and Zane, the Valiant-Vazirani
Lemma, and random walk ... more >>>


TR02-008 | 11th January 2002
Valentine Kabanets

Derandomization: A Brief Overview

This survey focuses on the recent (after 1998) developments in
the area of derandomization, with the emphasis on the derandomization of
time-bounded randomized complexity classes.

more >>>

TR02-028 | 15th May 2002
Eric Allender, Harry Buhrman, Michal Koucky, Detlef Ronneburger, Dieter van Melkebeek

Power from Random Strings

Revisions: 1 , Comments: 1

We consider sets of strings with high Kolmogorov complexity, mainly
in resource-bounded settings but also in the traditional
recursion-theoretic sense. We present efficient reductions, showing
that these sets are hard and complete for various complexity classes.

In particular, in addition to the usual Kolmogorov complexity measure
K, ... more >>>


TR02-038 | 5th June 2002
Rahul Santhanam

Resource Tradeoffs and Derandomization

Revisions: 1

We consider uniform assumptions for derandomization. We provide
intuitive evidence that BPP can be simulated non-trivially in
deterministic time by showing that (1) P \not \subseteq i.o.i.PLOYLOGSPACE
implies BPP \subseteq SUBEXP (2) P \not \subseteq SUBPSPACE implies BPP
= P. These results extend and complement earlier work of ... more >>>


TR02-039 | 30th June 2002
Oded Goldreich, Avi Wigderson

Derandomization that is rarely wrong from short advice that is typically good

Comments: 1

For every $\epsilon>0$,
we present a {\em deterministic}\/ log-space algorithm
that correctly decides undirected graph connectivity
on all but at most $2^{n^\epsilon}$ of the $n$-vertex graphs.
The same holds for every problem in Symmetric Log-space (i.e., $\SL$).

Making no assumptions (and in particular not assuming the ... more >>>


TR02-048 | 31st July 2002
Noga Alon, Oded Goldreich, Yishay Mansour

Almost $k$-wise independence versus $k$-wise independence


We say that a distribution over $\{0,1\}^n$
is almost $k$-wise independent
if its restriction to every $k$ coordinates results in a
distribution that is close to the uniform distribution.
A natural question regarding almost $k$-wise independent
distributions is how close they are to some $k$-wise
independent distribution. We show ... more >>>


TR02-055 | 13th September 2002
Valentine Kabanets, Russell Impagliazzo

Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds

Revisions: 1

We show that derandomizing Polynomial Identity Testing is,
essentially, equivalent to proving circuit lower bounds for
NEXP. More precisely, we prove that if one can test in polynomial
time (or, even, nondeterministic subexponential time, infinitely
often) whether a given arithmetic circuit over integers computes an
identically zero polynomial, then either ... more >>>


TR02-069 | 14th November 2002
Luca Trevisan

A Note on Deterministic Approximate Counting for k-DNF

Revisions: 1

We describe a deterministic algorithm that, for constant k,
given a k-DNF or k-CNF formula f and a parameter e, runs in time
linear in the size of f and polynomial in 1/e and returns an
estimate of the fraction of satisfying assignments for f up to ... more >>>


TR03-029 | 1st April 2003
Philippe Moser

BPP has effective dimension at most 1/2 unless BPP=EXP

We prove that BPP has Lutz's p-dimension at most 1/2 unless BPP equals EXP.
Next we show that BPP has Lutz's p-dimension zero unless BPP equals EXP
on infinitely many input lengths.
We also prove that BPP has measure zero in the smaller complexity
class ... more >>>


TR04-008 | 27th November 2003
Vikraman Arvind, Jacobo Toran

Solvable Group Isomorphism is (almost) in NP\cap coNP


The Group Isomorphism problem consists in deciding whether two input
groups $G_1$ and $G_2$ given by their multiplication tables are
isomorphic. We first give a 2-round Arthur-Merlin protocol for the
Group Non-Isomorphism problem such that on input groups $(G_1,G_2)$
of size $n$, Arthur uses ... more >>>


TR04-086 | 12th October 2004
Ronen Shaltiel, Chris Umans

Pseudorandomness for Approximate Counting and Sampling

We study computational procedures that use both randomness and nondeterminism. Examples are Arthur-Merlin games and approximate counting and sampling of NP-witnesses. The goal of this paper is to derandomize such procedures under the weakest possible assumptions.

Our main technical contribution allows one to ``boost'' a given hardness assumption. One special ... more >>>


TR04-094 | 10th November 2004
Omer Reingold

Undirected ST-Connectivity in Log-Space

We present a deterministic, log-space algorithm that solves
st-connectivity in undirected graphs. The previous bound on the
space complexity of undirected st-connectivity was
log^{4/3}() obtained by Armoni, Ta-Shma, Wigderson and
Zhou. As undirected st-connectivity is
complete for the class of problems solvable by symmetric,
non-deterministic, log-space computations (the class SL), ... more >>>


TR05-008 | 11th December 2004
Neeraj Kayal

Recognizing permutation functions in polynomial time.

Let $\mathbb{F}_q$ be a finite field and $f(x) \in \mathbb{F}_q(x)$ be a rational function over $\mathbb{F}_q$.
The decision problem {\bf PermFunction} consists of deciding whether $f(x)$ induces a permutation on
the elements of $\mathbb{F}_q$. That is, we want to decide whether the corresponding map
$f : \mathbb{F}_q ... more >>>


TR05-014 | 30th January 2005
Oded Goldreich

Short Locally Testable Codes and Proofs (Survey)


We survey known results regarding locally testable codes
and locally testable proofs (known as PCPs),
with emphasis on the length of these constructs.
Locally testability refers to approximately testing
large objects based on a very small number of probes,
each retrieving a single bit in the ... more >>>


TR05-018 | 6th February 2005
Oded Goldreich

On Promise Problems (a survey in memory of Shimon Even [1935-2004])


The notion of promise problems was introduced and initially studied
by Even, Selman and Yacobi
(Information and Control, Vol.~61, pages 159-173, 1984).
In this article we survey some of the applications that this
notion has found in the twenty years that elapsed.
These include the notion ... more >>>


TR05-022 | 19th February 2005
Omer Reingold, Luca Trevisan, Salil Vadhan

Pseudorandom Walks in Biregular Graphs and the RL vs. L Problem

Motivated by Reingold's recent deterministic log-space algorithm for Undirected S-T Connectivity (ECCC TR 04-94), we revisit the general RL vs. L question, obtaining the following results.

1. We exhibit a new complete problem for RL: S-T Connectivity restricted to directed graphs for which the random walk is promised to have ... more >>>


TR05-027 | 19th February 2005
Daniel Rolf

Derandomization of PPSZ for Unique-$k$-SAT

The PPSZ algorithm presented by Paturi, Pudlak, Saks, and Zane in 1998 has the nice feature that the only satisfying solution of a uniquely satisfiable $3$-SAT formulas can be found in expected running time at most $\Oc(1.3071^n).$ Using the technique of limited independence, we can derandomize this algorithm yielding $\Oc(1.3071^n)$ ... more >>>


TR05-042 | 15th April 2005
Lance Fortnow, Adam Klivans

Linear Advice for Randomized Logarithmic Space

Revisions: 1

We show that RL is contained in L/O(n), i.e., any language computable
in randomized logarithmic space can be computed in deterministic
logarithmic space with a linear amount of non-uniform advice. To
prove our result we show how to take an ultra-low space walk on
the Gabber-Galil expander graph.

more >>>

TR05-043 | 5th April 2005
Emanuele Viola

Pseudorandom Bits for Constant-Depth Circuits with Few Arbitrary Symmetric Gates

We exhibit an explicitly computable `pseudorandom' generator stretching $l$ bits into $m(l) = l^{\Omega(\log l)}$ bits that look random to constant-depth circuits of size $m(l)$ with $\log m(l)$ arbitrary symmetric gates (e.g. PARITY, MAJORITY). This improves on a generator by Luby, Velickovic and Wigderson (ISTCS '93) that achieves the same ... more >>>


TR05-045 | 12th April 2005
Philippe Moser

Martingale Families and Dimension in P

Revisions: 1

We introduce a new measure notion on small complexity classes (called F-measure), based on martingale families,
that get rid of some drawbacks of previous measure notions:
martingale families can make money on all strings,
and yield random sequences with an equal frequency of 0's and 1's.
As applications to F-measure,
more >>>


TR05-109 | 28th September 2005
Ariel Gabizon, Ran Raz, Ronen Shaltiel

Deterministic Extractors for Bit-fixing Sources by Obtaining an Independent Seed

An $(n,k)$-bit-fixing source is a distribution $X$ over $\B^n$ such that
there is a subset of $k$ variables in $X_1,\ldots,X_n$ which are uniformly
distributed and independent of each other, and the remaining $n-k$ variables
are fixed. A deterministic bit-fixing source extractor is a function $E:\B^n
\ar \B^m$ which on ... more >>>


TR05-160 | 10th December 2005
Xiaoyang Gu, Jack H. Lutz

Dimension Characterizations of Complexity Classes

We use derandomization to show that sequences of positive $\pspace$-dimension -- in fact, even positive $\Delta^\p_k$-dimension
for suitable $k$ -- have, for many purposes, the full power of random oracles. For example, we show that, if $S$ is any binary sequence whose $\Delta^p_3$-dimension is positive, then $\BPP\subseteq \P^S$ and, moreover, ... more >>>


TR06-002 | 4th January 2006
Eyal Kaplan, Moni Naor, Omer Reingold

Derandomized Constructions of k-Wise (Almost) Independent Permutations

Constructions of k-wise almost independent permutations have been receiving a growing amount of attention in recent years. However, unlike the case of k-wise independent functions, the size of previously constructed families of such permutations is far from optimal.

In this paper we describe a method for reducing the size of ... more >>>


TR06-058 | 25th April 2006
Alexander Healy

Randomness-Efficient Sampling within NC^1

Revisions: 1

We construct a randomness-efficient averaging sampler that is computable by uniform constant-depth circuits with parity gates (i.e., in AC^0[mod 2]). Our sampler matches the parameters achieved by random walks on constant-degree expander graphs, allowing us to apply a variety expander-based techniques within NC^1. For example, we obtain the following results:

... more >>>

TR06-105 | 23rd August 2006
Avi Wigderson, David Xiao

Derandomizing the AW matrix-valued Chernoff bound using pessimistic estimators and applications

Ahlswede and Winter introduced a Chernoff bound for matrix-valued random variables, which is a non-trivial generalization of the usual Chernoff bound for real-valued random variables. We present an efficient derandomization of their bound using the method of pessimistic estimators (see Raghavan). As a consequence, we derandomize a construction of Alon ... more >>>


TR07-012 | 22nd January 2007
Shachar Lovett, Sasha Sodin

Almost Euclidean sections of the N-dimensional cross-polytope using O(N) random bits

Revisions: 1

It is well known that $\R^N$ has subspaces of dimension
proportional to $N$ on which the $\ell_1$ norm is equivalent to the
$\ell_2$ norm; however, no explicit constructions are known.
Extending earlier work by Artstein--Avidan and Milman, we prove that
such a subspace can be generated using $O(N)$ random bits.

... more >>>

TR07-013 | 6th February 2007
Andris Ambainis, Joseph Emerson

Quantum t-designs: t-wise independence in the quantum world

A t-design for quantum states is a finite set of quantum states with the property of simulating the Haar-measure on quantum states w.r.t. any test that uses at most t copies of a state. We give efficient constructions for approximate quantum t-designs for arbitrary t.

We then show that an ... more >>>


TR07-030 | 29th March 2007
Kai-Min Chung, Omer Reingold, Salil Vadhan

S-T Connectivity on Digraphs with a Known Stationary Distribution

We present a deterministic logspace algorithm for solving s-t connectivity on directed graphs if (i) we are given a stationary distribution for random walk on the graph and (ii) the random walk which starts at the source vertex $s$ has polynomial mixing time. This result generalizes the recent deterministic logspace ... more >>>


TR07-057 | 11th July 2007
Oded Goldreich

On the Average-Case Complexity of Property Testing

Revisions: 1

Motivated by a recent study of Zimand (22nd CCC, 2007),
we consider the average-case complexity of property testing
(focusing, for clarity, on testing properties of Boolean strings).
We make two observations:

1) In the context of average-case analysis with respect to
the uniform distribution (on all strings of ... more >>>


TR07-059 | 6th July 2007
Shankar Kalyanaraman, Chris Umans

Algorithms for Playing Games with Limited Randomness

We study multiplayer games in which the participants have access to
only limited randomness. This constrains both the algorithms used to
compute equilibria (they should use little or no randomness) as well
as the mixed strategies that the participants are capable of playing
(these should be sparse). We frame algorithmic ... more >>>


TR07-069 | 29th July 2007
Ronen Shaltiel, Chris Umans

Low-end uniform hardness vs. randomness tradeoffs for AM

In 1998, Impagliazzo and Wigderson proved a hardness vs. randomness tradeoff for BPP in the {\em uniform setting}, which was subsequently extended to give optimal tradeoffs for the full range of possible hardness assumptions by Trevisan and Vadhan (in a slightly weaker setting). In 2003, Gutfreund, Shaltiel and Ta-Shma proved ... more >>>


TR07-081 | 10th August 2007
Andrej Bogdanov, Emanuele Viola

Pseudorandom bits for polynomials

We present a new approach to constructing pseudorandom generators that fool low-degree polynomials over finite fields, based on the Gowers norm. Using this approach, we obtain the following main constructions of explicitly computable generators $G : \F^s \to \F^n$ that fool polynomials over a prime field $\F$:
\begin{enumerate}
\item a ... more >>>


TR07-121 | 21st November 2007
Zeev Dvir, Amir Shpilka, Amir Yehudayoff

Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits

In this paper we show that lower bounds for bounded depth arithmetic circuits imply derandomization of polynomial identity testing for bounded depth arithmetic circuits. More formally, if there exists an explicit polynomial f(x_1,...,x_m) that cannot be computed by a depth d arithmetic circuit of small size then there exists ... more >>>


TR07-122 | 22nd November 2007
Zeev Dvir, Amir Shpilka

Towards Dimension Expanders Over Finite Fields

In this paper we study the problem of explicitly constructing a
{\em dimension expander} raised by \cite{BISW}: Let $\mathbb{F}^n$
be the $n$ dimensional linear space over the field $\mathbb{F}$.
Find a small (ideally constant) set of linear transformations from
$\F^n$ to itself $\{A_i\}_{i \in I}$ such that for every linear
more >>>


TR08-007 | 6th February 2008
Dan Gutfreund, Salil Vadhan

Limitations of Hardness vs. Randomness under Uniform Reductions

We consider (uniform) reductions from computing a function f to the task of distinguishing the output of some pseudorandom generator G from uniform. Impagliazzo and Wigderson (FOCS `98, JCSS `01) and Trevisan and Vadhan (CCC `02, CC `07) exhibited such reductions for every function f in PSPACE. Moreover, their reductions ... more >>>


TR08-049 | 10th April 2008
Vikraman Arvind, Partha Mukhopadhyay

Derandomizing the Isolation Lemma and Lower Bounds for Noncommutative Circuit Size

Revisions: 3

We give a randomized polynomial-time identity test for
noncommutative circuits of polynomial degree based on the isolation
lemma. Using this result, we show that derandomizing the isolation
lemma implies noncommutative circuit size lower bounds. More
precisely, we consider two restricted versions of the isolation
lemma and show that derandomizing each ... more >>>


TR08-062 | 11th June 2008
Manindra Agrawal, V Vinay

Arithmetic Circuits: A Chasm at Depth Four

We show that proving exponential lower bounds on depth four arithmetic
circuits imply exponential lower bounds for unrestricted depth arithmetic
circuits. In other words, for exponential sized circuits additional depth
beyond four does not help.

We then show that a complete black-box derandomization of Identity Testing problem for depth four ... more >>>


TR08-065 | 11th July 2008
Noga Alon, Rina Panigrahy, Sergey Yekhanin

Deterministic Approximation Algorithms for the Nearest Codeword Problem

The Nearest Codeword Problem (NCP) is a basic algorithmic question in the theory of error-correcting codes. Given a point v in an n-dimensional space over F_2 and a linear subspace L in F_2^n of dimension k NCP asks to find a point l in L that minimizes the (Hamming) distance ... more >>>


TR09-012 | 4th February 2009
Noga Alon, Shai Gutner

Balanced Hashing, Color Coding and Approximate Counting


Color Coding is an algorithmic technique for deciding efficiently
if a given input graph contains a path of a given length (or
another small subgraph of constant tree-width). Applications of the
method in computational biology motivate the study of similar
algorithms for counting the number of copies of a ... more >>>


TR09-032 | 16th April 2009
Neeraj Kayal, Shubhangi Saraf

Blackbox Polynomial Identity Testing for Depth 3 Circuits

We study depth three arithmetic circuits with bounded top fanin. We give the first deterministic polynomial time blackbox identity test for depth three circuits with bounded top fanin over the field of rational numbers, thus resolving a question posed by Klivans and Spielman (STOC 2001).

Our main technical result is ... more >>>


TR09-039 | 6th April 2009
Matei David, Periklis Papakonstantinou, Anastasios Sidiropoulos

Polynomial Time with Restricted Use of Randomness

We define a hierarchy of complexity classes that lie between P and RP, yielding a new way of quantifying partial progress towards the derandomization of RP. A standard approach in derandomization is to reduce the number of random bits an algorithm uses. We instead focus on a model of computation ... more >>>


TR09-063 | 29th July 2009
Matt DeVos, Ariel Gabizon

Simple Affine Extractors using Dimension Expansion

Revisions: 2

Let $\F$ be the field of $q$ elements. An \emph{\afsext{n}{k}} is a mapping $D:\F^n\ar\B$
such that for any $k$-dimensional affine subspace $X\subseteq \F^n$, $D(x)$ is an almost unbiased
bit when $x$ is chosen uniformly from $X$.
Loosely speaking, the problem of explicitly constructing affine extractors gets harder as $q$ gets ... more >>>


TR09-064 | 3rd August 2009
Harry Buhrman, Lance Fortnow, Rahul Santhanam

Unconditional Lower Bounds against Advice

We show several unconditional lower bounds for exponential time classes
against polynomial time classes with advice, including:
\begin{enumerate}
\item For any constant $c$, $\NEXP \not \subseteq \P^{\NP[n^c]}/n^c$
\item For any constant $c$, $\MAEXP \not \subseteq \MA/n^c$
\item $\BPEXP \not \subseteq \BPP/n^{o(1)}$
\end{enumerate}

It was previously unknown even whether $\NEXP \subseteq ... more >>>


TR09-070 | 1st September 2009
Andrej Bogdanov, Zeev Dvir, Elad Verbin, Amir Yehudayoff

Pseudorandomness for Width 2 Branching Programs

Bogdanov and Viola (FOCS 2007) constructed a pseudorandom
generator that fools degree $k$ polynomials over $\F_2$ for an arbitrary
constant $k$. We show that such generators can also be used to fool branching programs of width 2 and polynomial length that read $k$ bits of inputs at a
time. This ... more >>>


TR09-116 | 15th November 2009
Zohar Karnin, Partha Mukhopadhyay, Amir Shpilka, Ilya Volkovich

Deterministic identity testing of depth 4 multilinear circuits with bounded top fan-in

We give the first sub-exponential time deterministic polynomial
identity testing algorithm for depth-$4$ multilinear circuits with
a small top fan-in. More accurately, our algorithm works for
depth-$4$ circuits with a plus gate at the top (also known as
$\Spsp$ circuits) and has a running time of
$\exp(\poly(\log(n),\log(s),k))$ where $n$ is ... 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 >>>


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

Monotone expanders - constructions and applications

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


TR09-146 | 29th December 2009
Dan Gutfreund, Akinori Kawachi

Derandomizing Arthur-Merlin Games and Approximate Counting Implies Exponential-Size Lower Bounds

We show that if Arthur-Merlin protocols can be derandomized, then there is a Boolean function computable in deterministic exponential-time with access to an NP oracle, that cannot be computed by Boolean circuits of exponential size. More formally, if $\mathrm{prAM}\subseteq \mathrm{P}^{\mathrm{NP}}$ then there is a Boolean function in $\mathrm{E}^{\mathrm{NP}}$ that requires ... more >>>


TR10-015 | 8th February 2010
Maurice Jansen, Youming Qiao, Jayalal Sarma

Deterministic Black-Box Identity Testing $\pi$-Ordered Algebraic Branching Programs

In this paper we study algebraic branching programs (ABPs) with restrictions on the order and the number of reads of variables in the program. Given a permutation $\pi$ of $n$ variables, for a $\pi$-ordered ABP ($\pi$-OABP), for any directed path $p$ from source to sink, a variable can appear at ... more >>>


TR10-044 | 12th March 2010
Eli Ben-Sasson, Swastik Kopparty

Affine Dispersers from Subspace Polynomials

{\em Dispersers} and {\em extractors} for affine sources of dimension $d$ in $\mathbb F_p^n$ --- where $\mathbb F_p$ denotes the finite field of prime size $p$ --- are functions $f: \mathbb F_p^n \rightarrow \mathbb F_p$ that behave pseudorandomly when their domain is restricted to any particular affine space $S \subseteq ... more >>>


TR10-069 | 17th April 2010
Eric Allender, Vikraman Arvind, Fengming Wang

Uniform Derandomization from Pathetic Lower Bounds

Revisions: 1 , Comments: 1

A recurring theme in the literature on derandomization is that probabilistic
algorithms can be simulated quickly by deterministic algorithms, if one can obtain *impressive* (i.e., superpolynomial, or even nearly-exponential) circuit size lower bounds for certain problems. In contrast to what is
needed for derandomization, existing lower bounds seem rather pathetic ... more >>>


TR10-084 | 14th May 2010
Maurice Jansen, Youming Qiao, Jayalal Sarma

Deterministic Identity Testing of Read-Once Algebraic Branching Programs

An algebraic branching program (ABP) is given by a directed acyclic graph with source and sink vertices $s$ and $t$, respectively, and where edges are labeled by variables or field constants. An ABP computes the sum of weights of all directed paths from $s$ to $t$, where the weight of ... more >>>


TR10-088 | 17th May 2010
Jiri Sima, Stanislav Zak

A Polynomial Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3

Revisions: 2 , Comments: 3

The relationship between deterministic and probabilistic computations is one of the central issues in complexity theory. This problem can be tackled by constructing polynomial time hitting set generators which, however, belongs to the hardest problems in computer science even for severely restricted computational models. In our work, we consider read-once ... more >>>


TR10-098 | 17th June 2010
Daniel Kane, Jelani Nelson

A Derandomized Sparse Johnson-Lindenstrauss Transform

Revisions: 2

Recent work of [Dasgupta-Kumar-Sarl\'{o}s, STOC 2010] gave a sparse Johnson-Lindenstrauss transform and left as a main open question whether their construction could be efficiently derandomized. We answer their question affirmatively by giving an alternative proof of their result requiring only bounded independence hash functions. Furthermore, the sparsity bound obtained in ... more >>>


TR10-105 | 29th June 2010
Scott Aaronson, Dieter van Melkebeek

A note on circuit lower bounds from derandomization

We present an alternate proof of the result by Kabanets and Impagliazzo that derandomizing polynomial identity testing implies circuit lower bounds. Our proof is simpler, scales better, and yields a somewhat stronger result than the original argument.

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


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

Limits on the Computational Power of Random Strings

Revisions: 1

Let C(x) and K(x) denote plain and prefix Kolmogorov complexity, respectively, and let R_C and R_K denote the sets of strings that are ``random'' according to these measures; both R_K and R_C are undecidable. Earlier work has shown that every set in NEXP is in NP relative to both R_K ... more >>>


TR10-167 | 5th November 2010
Nitin Saxena, C. Seshadhri

Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn't matter

Let C be a depth-3 circuit with n variables, degree d and top fanin k (called sps(k,d,n) circuits) over base field F.
It is a major open problem to design a deterministic polynomial time blackbox algorithm
that tests if C is identically zero.
Klivans & Spielman (STOC 2001) observed ... more >>>


TR10-174 | 12th November 2010
Scott Aaronson, Baris Aydinlioglu, Harry Buhrman, John Hitchcock, Dieter van Melkebeek

A note on exponential circuit lower bounds from derandomizing Arthur-Merlin games

We present an alternate proof of the recent result by Gutfreund and Kawachi that derandomizing Arthur-Merlin games into $P^{NP}$ implies linear-exponential circuit lower bounds for $E^{NP}$. Our proof is simpler and yields stronger results. In particular, consider the promise-$AM$ problem of distinguishing between the case where a given Boolean circuit ... more >>>


TR10-188 | 8th December 2010
Matthew Anderson, Dieter van Melkebeek, Ilya Volkovich

Derandomizing Polynomial Identity Testing for Multilinear Constant-Read Formulae

Revisions: 1

We present a polynomial-time deterministic algorithm for testing whether constant-read multilinear arithmetic formulae are identically zero. In such a formula each variable occurs only a constant number of times and each subformula computes a multilinear polynomial. Our algorithm runs in time $s^{O(1)}\cdot n^{k^{O(k)}}$, where $s$ denotes the size of the ... more >>>


TR11-046 | 2nd April 2011
Shubhangi Saraf, Ilya Volkovich

Black-Box Identity Testing of Depth-4 Multilinear Circuits

We study the problem of identity testing for multilinear $\Spsp(k)$ circuits, i.e. multilinear depth-$4$ circuits with fan-in $k$ at the top $+$ gate. We give the first polynomial-time deterministic
identity testing algorithm for such circuits. Our results also hold in the black-box setting.

The running time of our algorithm is ... more >>>


TR11-049 | 9th April 2011
Noga Alon, Shachar Lovett

Almost k-wise vs. k-wise independent permutations, and uniformity for general group actions

A family of permutations in $S_n$ is $k$-wise independent if a uniform permutation chosen from the family maps any distinct $k$ elements to any distinct $k$ elements equally likely. Efficient constructions of $k$-wise independent permutations are known for $k=2$ and $k=3$, but are unknown for $k \ge 4$. In fact, ... more >>>


TR11-064 | 23rd April 2011
Mark Braverman

Towards deterministic tree code constructions

We present a deterministic operator on tree codes -- we call tree code product -- that allows one to deterministically combine two tree codes into a larger tree code. Moreover, if the original tree codes are efficiently encodable and decodable, then so is their product. This allows us to give ... more >>>


TR11-151 | 9th November 2011
Valentine Kabanets, Osamu Watanabe

Is the Valiant-Vazirani Isolation Lemma Improvable?

Revisions: 2

The Valiant-Vazirani Isolation Lemma [TCS, vol. 47, pp. 85--93, 1986] provides an efficient procedure for isolating a satisfying assignment of a given satisfiable circuit: given a Boolean circuit $C$ on $n$ input variables, the procedure outputs a new circuit $C'$ on the same $n$ input variables with the property that ... more >>>


TR12-080 | 18th June 2012
Baris Aydinlioglu, Dieter van Melkebeek

Nondeterministic Circuit Lower Bounds from Mildly Derandomizing Arthur-Merlin Games

In several settings derandomization is known to follow from circuit lower bounds that themselves are equivalent to the existence of pseudorandom generators. This leaves open the question whether derandomization implies the circuit lower bounds that are known to imply it, i.e., whether the ability to derandomize in *any* way implies ... more >>>


TR12-107 | 30th August 2012
Brendan Juba, Ryan Williams

Massive Online Teaching to Bounded Learners

We consider a model of teaching in which the learners are consistent and have bounded state, but are otherwise arbitrary. The teacher is non-interactive and ``massively open'': the teacher broadcasts a sequence of examples of an arbitrary target concept, intended for every possible on-line learning algorithm to learn from. We ... more >>>


TR12-115 | 11th September 2012
Michael Forbes, Amir Shpilka

Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs

Revisions: 1

We study the problem of obtaining efficient, deterministic, black-box polynomial identity testing (PIT) algorithms for read-once oblivious algebraic branching programs (ABPs). This class has an efficient, deterministic, white-box polynomial identity testing algorithm (due to Raz and Shpilka), but prior to this work had no known such black-box algorithm. Here we ... more >>>


TR12-146 | 7th November 2012
Venkatesan Guruswami, Chaoping Xing

List decoding Reed-Solomon, Algebraic-Geometric, and Gabidulin subcodes up to the Singleton bound

We consider Reed-Solomon (RS) codes whose evaluation points belong to a subfield, and give a linear-algebraic list decoding algorithm that can correct a fraction of errors approaching the code distance, while pinning down the candidate messages to a well-structured affine space of dimension a constant factor smaller than the code ... more >>>


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

Optimal Hitting Sets for Combinatorial Shapes

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


TR12-170 | 30th November 2012
Scott Aaronson, Travis Hance

Generalizing and Derandomizing Gurvits's Approximation Algorithm for the Permanent

Around 2002, Leonid Gurvits gave a striking randomized algorithm to approximate the permanent of an n×n matrix A. The algorithm runs in O(n^2/?^2) time, and approximates Per(A) to within ±?||A||^n additive error. A major advantage of Gurvits's algorithm is that it works for arbitrary matrices, not just for nonnegative matrices. ... more >>>


TR13-009 | 9th January 2013
Zahra Jafargholi, Emanuele Viola

3SUM, 3XOR, Triangles

Revisions: 1

We show that if one can solve 3SUM on a set of size $n$
in time $n^{1+\epsilon}$ then one can list $t$ triangles in a
graph with $m$ edges in time $\tilde
O(m^{1+\epsilon}t^{1/3+\epsilon'})$ for any $\epsilon' > 0$. This is a
reversal of Patrascu's reduction from 3SUM to
listing triangles ... more >>>


TR13-103 | 24th July 2013
Gábor Ivanyos, Marek Karpinski, Youming Qiao, Miklos Santha

Generalized Wong sequences and their applications to Edmonds' problems

We design two deterministic polynomial time algorithms for variants of a problem introduced by Edmonds in 1967: determine the rank of a matrix $M$ whose entries are homogeneous linear polynomials over the integers. Given a linear subspace $\mathcal{B}$ of the $n \times n$ matrices over some field $\mathbb{F}$, we consider ... more >>>


TR13-115 | 27th August 2013
Daniele Micciancio

Locally Dense Codes

The Minimum Distance Problem (MDP), i.e., the computational task of evaluating (exactly or approximately) the minimum distance of a linear code, is a well known NP-hard problem in coding theory. A key element in essentially all known proofs that MDP is NP-hard is the construction of a combinatorial object that ... more >>>


TR13-122 | 5th September 2013
Irit Dinur, Venkatesan Guruswami

PCPs via low-degree long code and hardness for constrained hypergraph coloring

Revisions: 1

We develop new techniques to incorporate the recently proposed ``short code" (a low-degree version of the long code) into the construction and analysis of PCPs in the classical ``Label Cover + Fourier Analysis'' framework. As a result, we obtain more size-efficient PCPs that yield improved hardness results for approximating CSPs ... more >>>


TR13-132 | 23rd September 2013
Michael Forbes, Ramprasad Saptharishi, Amir Shpilka

Pseudorandomness for Multilinear Read-Once Algebraic Branching Programs, in any Order

We give deterministic black-box polynomial identity testing algorithms for multilinear read-once oblivious algebraic branching programs (ROABPs), in n^(lg^2 n) time. Further, our algorithm is oblivious to the order of the variables. This is the first sub-exponential time algorithm for this model. Furthermore, our result has no known analogue in the ... more >>>


TR13-152 | 7th November 2013
Oded Goldreich, Avi Wigderson

On Derandomizing Algorithms that Err Extremely Rarely

Revisions: 2

{\em Does derandomization of probabilistic algorithms become easier when the number of ``bad'' random inputs is extremely small?}

In relation to the above question, we put forward the following {\em quantified derandomization challenge}:
For a class of circuits $\cal C$ (e.g., P/poly or $AC^0,AC^0[2]$) and a bounding function $B:\N\to\N$ (e.g., ... more >>>


TR14-003 | 10th January 2014
Zeev Dvir, Rafael Mendes de Oliveira, Amir Shpilka

Testing Equivalence of Polynomials under Shifts

Revisions: 2 , Comments: 1

Two polynomials $f, g \in F[x_1, \ldots, x_n]$ are called shift-equivalent if there exists a vector $(a_1, \ldots, a_n) \in {F}^n$ such that the polynomial identity $f(x_1+a_1, \ldots, x_n+a_n) \equiv g(x_1,\ldots,x_n)$ holds. Our main result is a new randomized algorithm that tests whether two given polynomials are shift equivalent. Our ... more >>>


TR14-017 | 9th February 2014
Eli Ben-Sasson, Emanuele Viola

Short PCPs with projection queries

We construct a PCP for NTIME(2$^n$) with constant
soundness, $2^n \poly(n)$ proof length, and $\poly(n)$
queries where the verifier's computation is simple: the
queries are a projection of the input randomness, and the
computation on the prover's answers is a 3CNF. The
previous upper bound for these two computations was
more >>>


TR14-067 | 4th May 2014
Venkatesan Guruswami, Madhu Sudan, Ameya Velingker, Carol Wang

Limitations on Testable Affine-Invariant Codes in the High-Rate Regime

Locally testable codes (LTCs) of constant distance that allow the tester to make a linear number of queries have become the focus of attention recently, due to their elegant connections to hardness of approximation. In particular, the binary Reed-Muller code of block length $N$ and distance $d$ is known to ... more >>>


TR14-157 | 27th November 2014
Rafael Mendes de Oliveira, Amir Shpilka, Ben Lee Volk

Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas

In this paper we give subexponential size hitting sets for bounded depth multilinear arithmetic formulas. Using the known relation between black-box PIT and lower bounds we obtain lower bounds for these models.

For depth-3 multilinear formulas, of size $\exp(n^\delta)$, we give a hitting set of size $\exp(\tilde{O}(n^{2/3 + 2\delta/3}))$. ... more >>>


TR14-161 | 27th November 2014
Rahul Arora, Ashu Gupta, Rohit Gurjar, Raghunath Tewari

Derandomizing Isolation Lemma for $K_{3,3}$-free and $K_5$-free Bipartite Graphs

Revisions: 2

The perfect matching problem has a randomized $NC$ algorithm, using the celebrated Isolation Lemma of Mulmuley, Vazirani and Vazirani. The Isolation Lemma states that giving a random weight assignment to the edges of a graph, ensures that it has a unique minimum weight perfect matching, with a good probability. We ... more >>>


TR14-168 | 8th December 2014
Ilya Volkovich

Deterministically Factoring Sparse Polynomials into Multilinear Factors

We present the first efficient deterministic algorithm for factoring sparse polynomials that split into multilinear factors.
Our result makes partial progress towards the resolution of the classical question posed by von zur Gathen and Kaltofen in \cite{GathenKaltofen85} to devise an efficient deterministic algorithm for factoring (general) sparse polynomials.
We achieve ... more >>>


TR15-006 | 6th January 2015
Nader Bshouty

Dense Testers: Almost Linear Time and Locally Explicit Constructions

We develop a new notion called {\it $(1-\epsilon)$-tester for a
set $M$ of functions} $f:A\to C$. A $(1-\epsilon)$-tester
for $M$ maps each element $a\in A$ to a finite number of
elements $B_a=\{b_1,\ldots,b_t\}\subset B$ in a smaller
sub-domain $B\subset A$ where for every $f\in M$ if
$f(a)\not=0$ then $f(b)\not=0$ for at ... more >>>


TR15-042 | 30th March 2015
Ilya Volkovich

Computations beyond Exponentiation Gates and Applications

In Arithmetic Circuit Complexity the standard operations are $\{+,\times\}$.
Yet, in some scenarios exponentiation gates are considered as well (see e.g. \cite{BshoutyBshouty98,ASSS12,Kayal12,KSS14}).
In this paper we study the question of efficiently evaluating a polynomial given an oracle access to its power.
That is, beyond an exponentiation gate. As ... more >>>


TR15-076 | 28th April 2015
Mahdi Cheraghchi, Piotr Indyk

Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform

For every fixed constant $\alpha > 0$, we design an algorithm for computing the $k$-sparse Walsh-Hadamard transform of an $N$-dimensional vector $x \in \mathbb{R}^N$ in time $k^{1+\alpha} (\log N)^{O(1)}$. Specifically, the algorithm is given query access to $x$ and computes a $k$-sparse $\tilde{x} \in \mathbb{R}^N$ satisfying $\|\tilde{x} - \hat{x}\|_1 \leq ... more >>>


TR15-158 | 27th September 2015
Ofer Grossman, Dana Moshkovitz

Amplification and Derandomization Without Slowdown

We present techniques for decreasing the error probability of randomized algorithms and for converting randomized algorithms to deterministic (non-uniform) algorithms. Unlike most existing techniques that involve repetition of the randomized algorithm, and hence a slowdown, our techniques produce algorithms with a similar run-time to the original randomized algorithms.

The ... more >>>


TR15-177 | 9th November 2015
Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf

Bipartite Perfect Matching is in quasi-NC

Revisions: 2

We show that the bipartite perfect matching problem is in quasi-NC$^2$. That is, it has uniform circuits of quasi-polynomial size and $O(\log^2 n)$ depth. Previously, only an exponential upper bound was known on the size of such circuits with poly-logarithmic depth.

We obtain our result by an almost complete ... more >>>


TR15-187 | 24th November 2015
Nir Bitansky, Vinod Vaikuntanathan

A Note on Perfect Correctness by Derandomization

Revisions: 1


In this note, we show how to transform a large class of erroneous cryptographic schemes into perfectly correct ones. The transformation works for schemes that are correct on every input with probability noticeably larger than half, and are secure under parallel repetition. We assume the existence of one-way functions ... more >>>


TR16-050 | 31st March 2016
Roei Tell

Lower Bounds on Black-Box Reductions of Hitting to Density Estimation

Revisions: 1

We consider the following problem. A deterministic algorithm tries to find a string in an unknown set $S\subseteq\{0,1\}^n$ that is guaranteed to have large density (e.g., $|S|\ge2^{n-1}$). However, the only information that the algorithm can obtain about $S$ is estimates of the density of $S$ in adaptively chosen subsets of ... more >>>


TR16-083 | 23rd May 2016
Nader Bshouty

Derandomizing Chernoff Bound with Union Bound with an Application to $k$-wise Independent Sets

Derandomization of Chernoff bound with union bound is already proven in many papers.
We here give another explicit version of it that obtains a construction of size
that is arbitrary close to the probabilistic nonconstructive size.

We apply this to give a new simple polynomial time constructions of
almost $k$-wise ... more >>>


TR16-100 | 27th June 2016
Suguru Tamaki

A Satisfiability Algorithm for Depth Two Circuits with a Sub-Quadratic Number of Symmetric and Threshold Gates

We consider depth 2 unbounded fan-in circuits with symmetric and linear threshold gates. We present a deterministic algorithm that, given such a circuit with $n$ variables and $m$ gates, counts the number of satisfying assignments in time $2^{n-\Omega\left(\left(\frac{n}{\sqrt{m} \cdot \poly(\log n)}\right)^a\right)}$ for some constant $a>0$. Our algorithm runs in time ... more >>>


TR16-182 | 14th November 2016
Rohit Gurjar, Thomas Thierauf

Linear Matroid Intersection is in quasi-NC

Given two matroids on the same ground set, the matroid intersection problem asks to find a common independent set of maximum size. We show that the linear matroid intersection problem is in quasi-NC$^2$. That is, it has uniform circuits of quasi-polynomial size $n^{O(\log n)}$, and $O(\log^2 n)$ depth. This generalizes ... more >>>


TR16-191 | 24th November 2016
Roei Tell

Improved Bounds for Quantified Derandomization of Constant-Depth Circuits and Polynomials

Revisions: 3

Goldreich and Wigderson (STOC 2014) initiated a study of quantified derandomization, which is a relaxed derandomization problem: For a circuit class $\mathcal{C}$ and a parameter $B=B(n)$, the problem is to decide whether a circuit $C\in\mathcal{C}$ rejects all of its inputs, or accepts all but $B(n)$ of its inputs.

In ... more >>>


TR16-199 | 15th December 2016
Pavel Hubacek, Moni Naor, Eylon Yogev

The Journey from NP to TFNP Hardness

The class TFNP is the search analog of NP with the additional guarantee that any instance has a solution. TFNP has attracted extensive attention due to its natural syntactic subclasses that capture the computational complexity of important search problems from algorithmic game theory, combinatorial optimization and computational topology. Thus, one ... more >>>


TR17-052 | 19th March 2017
Dieter van Melkebeek, Gautam Prakriya

Derandomizing Isolation in Space-Bounded Settings

We study the possibility of deterministic and randomness-efficient isolation in space-bounded models of computation: Can one efficiently reduce instances of computational problems to equivalent instances that have at most one solution? We present results for the NL-complete problem of reachability on digraphs, and for the LogCFL-complete problem of certifying acceptance ... more >>>


TR17-146 | 1st October 2017
Or Meir

On Derandomized Composition of Boolean Functions

Revisions: 4

The composition of two Boolean functions $f:\left\{0,1\right\}^{m}\to\left\{0,1\right\}$, $g:\left\{0,1\right\}^{n}\to\left\{0,1\right\}$
is the function $f \diamond g$ that takes as inputs $m$ strings $x_{1},\ldots,x_{m}\in\left\{0,1\right\}^{n}$
and computes
\[
(f \diamond g)(x_{1},\ldots,x_{m})=f\left(g(x_{1}),\ldots,g(x_{m})\right).
\]
This operation has been used several times for amplifying different
hardness measures of $f$ and $g$. This comes at a cost: the ... more >>>


TR17-188 | 22nd December 2017
Cody Murray, Ryan Williams

Circuit Lower Bounds for Nondeterministic Quasi-Polytime: An Easy Witness Lemma for NP and NQP

We prove that if every problem in $NP$ has $n^k$-size circuits for a fixed constant $k$, then for every $NP$-verifier and every yes-instance $x$ of length $n$ for that verifier, the verifier's search space has an $n^{O(k^3)}$-size witness circuit: a witness for $x$ that can be encoded with a circuit ... more >>>


TR18-003 | 2nd January 2018
Roei Tell

Proving that prBPP=prP is as hard as "almost" proving that P \ne NP

Revisions: 5

We show that any proof that $promise\textrm{-}\mathcal{BPP}=promise\textrm{-}\mathcal{P}$ necessitates proving circuit lower bounds that almost yield that $\mathcal{P}\ne\mathcal{NP}$. More accurately, we show that if $promise\textrm{-}\mathcal{BPP}=promise\textrm{-}\mathcal{P}$, then for essentially any super-constant function $f(n)=\omega(1)$ it holds that $NTIME[n^{f(n)}]\not\subseteq\mathcal{P}/\mathrm{poly}$. The conclusion of the foregoing conditional statement cannot be improved (to conclude that $\mathcal{NP}\not\subseteq\mathcal{P}/\mathrm{poly}$) without ... more >>>


TR18-051 | 15th March 2018
Stasys Jukna

Derandomizing Dynamic Programming and Beyond

Revisions: 1

We consider probabilistic circuits working over the real numbers, and using arbitrary semialgebraic functions of bounded description complexity as gates. We show that such circuits can be simulated by deterministic circuits with an only polynomial blowup in size. An algorithmic consequence is that randomization cannot substantially speed up dynamic programming. ... more >>>


TR18-092 | 4th May 2018
Marco Carmosino, Russell Impagliazzo, Manuel Sabin

Fine-Grained Derandomization: From Problem-Centric to Resource-Centric Complexity

We show that popular hardness conjectures about problems from the field of fine-grained complexity theory imply structural results for resource-based complexity classes. Namely, we show that if either k-Orthogonal Vectors or k-CLIQUE requires $n^{\epsilon k}$ time, for some constant $\epsilon > 1/2$, to count (note that these conjectures are significantly ... more >>>


TR18-115 | 11th June 2018
Valentine Kabanets, Zhenjian Lu

Satisfiability and Derandomization for Small Polynomial Threshold Circuits

A polynomial threshold function (PTF) is defined as the sign of a polynomial $p\colon\bool^n\to\mathbb{R}$. A PTF circuit is a Boolean circuit whose gates are PTFs. We study the problems of exact and (promise) approximate counting for PTF circuits of constant depth.

Satisfiability (#SAT). We give the first zero-error randomized algorithm ... more >>>


TR18-122 | 3rd July 2018
Igor Carboni Oliveira, Rahul Santhanam

Pseudo-derandomizing learning and approximation

We continue the study of pseudo-deterministic algorithms initiated by Gat and Goldwasser
[GG11]. A pseudo-deterministic algorithm is a probabilistic algorithm which produces a fixed
output with high probability. We explore pseudo-determinism in the settings of learning and ap-
proximation. Our goal is to simulate known randomized algorithms in these settings ... more >>>


TR18-151 | 29th August 2018
Ankit Garg, Rafael Oliveira

Recent progress on scaling algorithms and applications

Scaling problems have a rich and diverse history, and thereby have found numerous
applications in several fields of science and engineering. For instance, the matrix scaling problem
has had applications ranging from theoretical computer science to telephone forecasting,
economics, statistics, optimization, among many other fields. Recently, a generalization of matrix
more >>>


TR18-206 | 3rd December 2018
Arkadev Chattopadhyay, Shachar Lovett, Marc Vinyals

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


TR19-010 | 21st January 2019
Dorit Aharonov, Alex Bredariol Grilo

Stoquastic PCP vs. Randomness

The derandomization of MA, the probabilistic version of NP, is a long standing open question. In this work, we connect this problem to a variant of another major problem: the quantum PCP conjecture. Our connection goes through the surprising quantum characterization of MA by Bravyi and Terhal. They proved the ... more >>>


TR19-065 | 1st May 2019
Mrinal Kumar, Ramprasad Saptharishi, Noam Solomon

Derandomization from Algebraic Hardness: Treading the Borders

Revisions: 3

A hitting-set generator (HSG) is a polynomial map $Gen:\mathbb{F}^k \to \mathbb{F}^n$ such that for all $n$-variate polynomials $Q$ of small enough circuit size and degree, if $Q$ is non-zero, then $Q\circ Gen$ is non-zero. In this paper, we give a new construction of such a HSG assuming that we have ... more >>>


TR19-075 | 25th May 2019
Lijie Chen, Dylan McKay, Cody Murray, Ryan Williams

Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems

Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems

A frontier open problem in circuit complexity is to prove P^NP is not in SIZE[n^k] for all k; this is a necessary intermediate step towards NP is not in P/poly. Previously, for several classes containing P^NP, including NP^NP, ZPP^NP, and ... more >>>


TR19-099 | 29th July 2019
Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman

Nearly Optimal Pseudorandomness From Hardness

Revisions: 3

Existing proofs that deduce $\mathbf{BPP}=\mathbf{P}$ from circuit lower bounds convert randomized algorithms into deterministic algorithms with a large polynomial slowdown. We convert randomized algorithms into deterministic ones with little slowdown. Specifically, assuming exponential lower bounds against nondeterministic circuits, we convert any randomized algorithm over inputs of length $n$ running in ... more >>>


TR19-119 | 9th September 2019
Dean Doron, Amnon Ta-Shma, Roei Tell

On Hitting-Set Generators for Polynomials that Vanish Rarely

Revisions: 1

We study the following question: Is it easier to construct a hitting-set generator for polynomials $p:\mathbb{F}^n\rightarrow\mathbb{F}$ of degree $d$ if we are guaranteed that the polynomial vanishes on at most an $\epsilon>0$ fraction of its inputs? We will specifically be interested in tiny values of $\epsilon\ll d/|\mathbb{F}|$. This question was ... more >>>


TR19-167 | 21st November 2019
Anant Dhayal, Russell Impagliazzo

UTIME Easy-witness Lemma & Some Consequences

Revisions: 2

We prove an easy-witness lemma ($\ewl$) for unambiguous non-deterministic verfiers. We show that if $\utime(t)\subset\mathcal{C}$, then for every $L\in\utime(t)$, for every $\utime(t)$ verifier $V$ for $L$, and for every $x\in L$, there is a certificate $y$ satisfing $V(x,y)=1$, that can be encoded as a truth-table of a $\mathcal{C}$ circuit. Our ... more >>>


TR20-010 | 12th February 2020
Lijie Chen, Hanlin Ren

Strong Average-Case Circuit Lower Bounds from Non-trivial Derandomization

Revisions: 1

We prove that for all constants a, NQP = NTIME[n^{polylog(n)}] cannot be (1/2 + 2^{-log^a n})-approximated by 2^{log^a n}-size ACC^0 of THR circuits (ACC^0 circuits with a bottom layer of THR gates). Previously, it was even open whether E^NP can be (1/2+1/sqrt{n})-approximated by AC^0[2] circuits. As a straightforward application, ... more >>>


TR20-026 | 25th February 2020
Dean Doron, Jack Murtagh, Salil Vadhan, David Zuckerman

Spectral Sparsification via Bounded-Independence Sampling

Revisions: 1

We give a deterministic, nearly logarithmic-space algorithm for mild spectral sparsification of undirected graphs. Given a weighted, undirected graph $G$ on $n$ vertices described by a binary string of length $N$, an integer $k\leq \log n$ and an error parameter $\varepsilon > 0$, our algorithm runs in space $\tilde{O}(k\log (N\cdot ... more >>>


TR20-042 | 31st March 2020
Pranav Bisht, Nitin Saxena

Poly-time blackbox identity testing for sum of log-variate constant-width ROABPs

Blackbox polynomial identity testing (PIT) affords 'extreme variable-bootstrapping' (Agrawal et al, STOC'18; PNAS'19; Guo et al, FOCS'19). This motivates us to study log-variate read-once oblivious algebraic branching programs (ROABP). We restrict width of ROABP to a constant and study the more general sum-of-ROABPs model. We give the first poly($s$)-time blackbox ... more >>>


TR20-043 | 29th March 2020
Dorit Aharonov, Alex Bredariol Grilo

A combinatorial MA-complete problem

Revisions: 2

Despite the interest in the complexity class MA, the randomized analog of NP, there is just a couple of known natural (promise-)MA-complete problems, the first due to Bravyi and Terhal (SIAM Journal of Computing 2009) and the second due to Bravyi (Quantum Information and Computation 2015). Surprisingly, both problems are ... more >>>


TR20-059 | 16th April 2020
Gonen Krak, Noam Parzanchevski, Amnon Ta-Shma

Pr-ZSUBEXP is not contained in Pr-RP

Revisions: 1

We unconditionally prove there exists a promise problem in promise ZSUBEXP that cannot be solved in promise RP.
The proof technique builds upon Kabanets' easy witness method [Kab01] as implemented by Impagliazzo et. al [IKW02], with a separate diagonalization carried out on each of the two alternatives in the ... more >>>


TR20-069 | 4th May 2020
Eshan Chattopadhyay, Jyun-Jie Liao

Optimal Error Pseudodistributions for Read-Once Branching Programs

Revisions: 1

In a seminal work, Nisan (Combinatorica'92) constructed a pseudorandom generator for length $n$ and width $w$ read-once branching programs with seed length $O(\log n\cdot \log(nw)+\log n\cdot\log(1/\varepsilon))$ and error $\varepsilon$. It remains a central question to reduce the seed length to $O(\log (nw/\varepsilon))$, which would prove that $\mathbf{BPL}=\mathbf{L}$. However, there has ... more >>>


TR20-148 | 28th September 2020
Lijie Chen, Roei Tell

Simple and fast derandomization from very hard functions: Eliminating randomness at almost no cost

Revisions: 1

Extending the classical ``hardness-to-randomness'' line-of-works, Doron et al. (FOCS 2020) recently proved that derandomization with near-quadratic time overhead is possible, under the assumption that there exists a function in $\mathcal{DTIME}[2^n]$ that cannot be computed by randomized SVN circuits of size $2^{(1-\epsilon)\cdot n}$ for a small $\epsilon$.

In this work we ... more >>>


TR20-150 | 7th October 2020
Lijie Chen, Xin Lyu, Ryan Williams

Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization

In certain complexity-theoretic settings, it is notoriously difficult to prove complexity separations which hold almost everywhere, i.e., for all but finitely many input lengths. For example, a classical open question is whether $\mathrm{NEXP} \subset \mathrm{i.o.-}\mathrm{NP}$; that is, it is open whether nondeterministic exponential time computations can be simulated on infinitely ... more >>>


TR21-013 | 20th January 2021
Srinivasan Arunachalam, Penghui Yao

Positive spectrahedrons: Geometric properties, Invariance principles and Pseudorandom generators

In a recent work, O'Donnell, Servedio and Tan (STOC 2019) gave explicit pseudorandom generators (PRGs) for arbitrary $m$-facet polytopes in $n$ variables with seed length poly-logarithmic in $m,n$, concluding a sequence of works in the last decade, that was started by Diakonikolas, Gopalan, Jaiswal, Servedio, Viola (SICOMP 2010) and Meka, ... more >>>


TR21-080 | 10th June 2021
Lijie Chen, Roei Tell

Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise

We propose a new approach to the hardness-to-randomness framework and to the promise-BPP=promise-P conjecture. Classical results rely on non-uniform hardness assumptions to construct derandomization algorithms that work in the worst-case, or rely on uniform hardness assumptions to construct derandomization algorithms that work only in the average-case. In both types of ... more >>>


TR21-120 | 18th August 2021
Roei Tell

How to Find Water in the Ocean: A Survey on Quantified Derandomization

The focus of this survey is the question of *quantified derandomization*, which was introduced by Goldreich and Wigderson (2014): Does derandomization of probabilistic algorithms become easier if we only want to derandomize algorithms that err with extremely small probability? How small does this probability need to be in order for ... more >>>


TR21-153 | 9th November 2021
Ronen Shaltiel, Emanuele Viola

On Hardness Assumptions Needed for "Extreme High-End" PRGs and Fast Derandomization

Revisions: 1

The hardness vs.~randomness paradigm aims to explicitly construct pseudorandom generators $G:\{0,1\}^r \to \{0,1\}^m$ that fool circuits of size $m$, assuming the existence of explicit hard functions. A ``high-end PRG'' with seed length $r=O(\log m)$ (implying BPP=P) was achieved in a seminal work of Impagliazzo and Wigderson (STOC 1997), assuming \textsc{the ... more >>>


TR21-179 | 8th December 2021
tatsuie tsukiji

Smoothed Complexity of Learning Disjunctive Normal Forms, Inverting Fourier Transforms, and Verifying Small Circuits

Comments: 1

This paper aims to derandomize the following problems in the smoothed analysis of Spielman and Teng. Learn Disjunctive Normal Form (DNF), invert Fourier Transforms (FT), and verify small circuits' unsatisfiability. Learning algorithms must predict a future observation from the only $m$ i.i.d. samples of a fixed but unknown joint-distribution $P(G(x),y)$ ... more >>>


TR22-004 | 3rd January 2022
Silas Richelson, Sourya Roy

Analyzing Ta-Shma’s Code via the Expander Mixing Lemma

Random walks in expander graphs and their various derandomizations (e.g., replacement/zigzag product) are invaluable tools from pseudorandomness. Recently, Ta-Shma used s-wide replacement walks in his breakthrough construction of a binary linear code almost matching the Gilbert-Varshamov bound (STOC 2017). Ta-Shma’s original analysis was entirely linear algebraic, and subsequent developments have ... more >>>


TR22-008 | 14th January 2022
Gil Cohen, Dean Doron, Ori Sberlo

Approximating Large Powers of Stochastic Matrices in Small Space

Comments: 1

We give a deterministic space-efficient algorithm for approximating powers of stochastic matrices. On input a $w \times w$ stochastic matrix $A$, our algorithm approximates $A^{n}$ in space $\widetilde{O}(\log n + \sqrt{\log n}\cdot \log w)$ to within high accuracy. This improves upon the seminal work by Saks and Zhou (FOCS'95), that ... more >>>


TR22-010 | 18th January 2022
Marshall Ball, Dana Dachman-Soled, Julian Loss

(Nondeterministic) Hardness vs. Non-Malleability

We present the first truly explicit constructions of \emph{non-malleable codes} against tampering by bounded polynomial size circuits. These objects imply unproven circuit lower bounds and our construction is secure provided E requires exponential size nondeterministic circuits, an assumption from the derandomization literature.

Prior works on NMC ... more >>>


TR22-021 | 19th February 2022
Xin Lyu

Improved Pseudorandom Generators for $\mathrm{AC}^0$ Circuits

We give PRG for depth-$d$, size-$m$ $\mathrm{AC}^0$ circuits with seed length $O(\log^{d-1}(m)\log(m/\varepsilon)\log\log(m))$. Our PRG improves on previous work [TX13, ST19, Kel21] from various aspects. It has optimal dependence on $\frac{1}{\varepsilon}$ and is only one “$\log\log(m)$” away from the lower bound barrier. For the case of $d=2$, the seed length tightly ... more >>>


TR22-057 | 25th April 2022
Lijie Chen, Roei Tell

When Arthur has Neither Random Coins nor Time to Spare: Superfast Derandomization of Proof Systems

Revisions: 2

What is the actual cost of derandomization? And can we get it for free? These questions were recently raised by Doron et. al (FOCS 2020) and have been attracting considerable interest. In this work we extend the study of these questions to the setting of *derandomizing interactive proofs systems*.

... more >>>

TR22-060 | 27th April 2022
Nikolay Vereshchagin

How much randomness is needed to convert MA protocols to AM protocols?

The Merlin-Arthur class of languages MA is included into Arthur-Merlin class AM, and into PP. For a standard transformation of a given MA protocol with Arthur's message (= random string) of length $a$ and Merlin's message of length $m$ to a PP machine, the latter needs $O(ma)$ random bits. The ... more >>>


TR22-070 | 8th May 2022
Pranav Bisht, Ilya Volkovich

On Solving Sparse Polynomial Factorization Related Problems

Revisions: 6

In a recent result of Bhargava, Saraf and Volkovich [FOCS’18; JACM’20], the first sparsity bound for constant individual degree polynomials was shown. In particular, it was shown that any factor of a polynomial with at most $s$ terms and individual degree bounded by $d$ can itself have at most $s^{O(d^2\log ... more >>>


TR22-084 | 2nd June 2022
Yanyi Liu, Rafael Pass

Characterizing Derandomization Through Hardness of Levin-Kolmogorov Complexity

A central open problem in complexity theory concerns the question of whether all efficient randomized algorithms can be simulated by efficient deterministic algorithms. We consider this problem in the context of promise problems (i.e,. the $\prBPP$ v.s. $\prP$ problem) and show that for all sufficiently large constants $c$, the following ... more >>>


TR22-097 | 3rd July 2022
Lijie Chen, Ron D. Rothblum, Roei Tell

Unstructured Hardness to Average-Case Randomness

The leading technical approach in uniform hardness-to-randomness in the last two decades faced several well-known barriers that caused results to rely on overly strong hardness assumptions, and yet still yield suboptimal conclusions.

In this work we show uniform hardness-to-randomness results that *simultaneously break through all of the known barriers*. Specifically, ... more >>>


TR22-121 | 27th August 2022
William Hoza

Recent Progress on Derandomizing Space-Bounded Computation

Revisions: 1

Is randomness ever necessary for space-efficient computation? It is commonly conjectured that L = BPL, meaning that halting decision algorithms can always be derandomized without increasing their space complexity by more than a constant factor. In the past few years (say, from 2017 to 2022), there has been some exciting ... more >>>


TR22-122 | 29th August 2022
Young Kun Ko

Efficient Linearization Implies the Multiphase Conjecture

The main motivation for studying linear data structures and circuits is the intuition that non-linear advice cannot help in computing a linear operator. Jukna and Schnitger formalized this as a conjecture which states that all circuits computing a linear operator can be ``linearized," with only a constant size blow-up. We ... more >>>


TR22-169 | 26th November 2022
Zeyu Guo, Ben Lee Volk, Akhil Jalan, David Zuckerman

Extractors for Images of Varieties

Revisions: 1

We construct explicit deterministic extractors for polynomial images of varieties, that is, distributions sampled by applying a low-degree polynomial map $f : \mathbb{F}_q^r \to \mathbb{F}_q^n$ to an element sampled uniformly at random from a $k$-dimensional variety $V \subseteq \mathbb{F}_q^r$. This class of sources generalizes both polynomial sources, studied by Dvir, ... more >>>


TR22-170 | 15th November 2022
Huck Bennett

The Complexity of the Shortest Vector Problem

Revisions: 1

Computational problems on point lattices play a central role in many areas of computer science including integer programming, coding theory, cryptanalysis, and especially the design of secure cryptosystems. In this survey, we present known results and open questions related to the complexity of the most important of these problems, the ... more >>>


TR22-183 | 19th December 2022
Lijie Chen

New Lower Bounds and Derandomization for ACC, and a Derandomization-centric View on the Algorithmic Method

In this paper, we obtain several new results on lower bounds and derandomization for ACC^0 circuits (constant-depth circuits consisting of AND/OR/MOD_m gates for a fixed constant m, a frontier class in circuit complexity):

1. We prove that any polynomial-time Merlin-Arthur proof system with an ACC^0 verifier (denoted by ... more >>>


TR23-070 | 9th May 2023
Shuichi Hirahara, Zhenjian Lu, Hanlin Ren

Bounded Relativization

Relativization is one of the most fundamental concepts in complexity theory, which explains the difficulty of resolving major open problems. In this paper, we propose a weaker notion of relativization called *bounded relativization*. For a complexity class $C$, we say that a statement is *$C$-relativizing* if the statement holds relative ... more >>>


TR23-105 | 13th July 2023
Lijie Chen, Roei Tell, Ryan Williams

Derandomization vs Refutation: A Unified Framework for Characterizing Derandomization

We establish an equivalence between two algorithmic tasks: *derandomization*, the deterministic simulation of probabilistic algorithms; and *refutation*, the deterministic construction of inputs on which a given probabilistic algorithm fails to compute a certain hard function.

We prove that refuting low-space probabilistic streaming algorithms that try to compute functions $f\in\mathcal{FP}$ ... more >>>


TR23-109 | 21st July 2023
Pranav Bisht, Nikhil Gupta, Ilya Volkovich

Towards Identity Testing for Sums of Products of Read-Once and Multilinear Bounded-Read Formulae

An arithmetic formula is an arithmetic circuit where each gate has fan-out one. An \emph{arithmetic read-once formula} (ROF in short) is an arithmetic formula where each input variable labels at most one leaf. In this paper we present several efficient blackbox \emph{polynomial identity testing} (PIT) algorithms for some classes of ... more >>>


TR23-114 | 8th August 2023
Lijie Chen, William Hoza, Xin Lyu, Avishay Tal, Hongxun Wu

Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and Shortcutting

A weighted pseudorandom generator (WPRG) is a generalization of a pseudorandom generator (PRG) in which, roughly speaking, probabilities are replaced with weights that are permitted to be positive or negative. We present new explicit constructions of WPRGs that fool certain classes of standard-order read-once branching programs. In particular, our WPRGs ... more >>>


TR23-130 | 8th September 2023
Eshan Chattopadhyay, Jyun-Jie Liao

Recursive Error Reduction for Regular Branching Programs

Revisions: 1

In a recent work, Chen, Hoza, Lyu, Tal and Wu (FOCS 2023) showed an improved error reduction framework for the derandomization of regular read-once branching programs (ROBPs). Their result is based on a clever modification to the inverse Laplacian perspective of space-bounded derandomization, which was originally introduced by Ahmadinejad, Kelner, ... more >>>


TR24-041 | 1st March 2024
Pranav Bisht, Nikhil Gupta, Prajakta Nimbhorkar, Ilya Volkovich

Launching Identity Testing into (Bounded) Space

In this work, we initiate the study of the space complexity of the Polynomial Identity Testing problem (PIT).
First, we observe that the majority of the existing (time-)efficient ``blackbox'' PIT algorithms already give rise to space-efficient ``whitebox'' algorithms for the respective classes of arithmetic formulas via a space-efficient ... more >>>




ISSN 1433-8092 | Imprint