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

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

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

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

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

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

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

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

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

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

ISSN 1433-8092 | Imprint