Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



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

D
TR16-202 | 19th December 2016
Dmitry Sokolov

Dag-like Communication and Its Applications

Revisions: 1

In 1990 Karchmer and Widgerson considered the following communication problem $Bit$: Alice and Bob know a function $f: \{0, 1\}^n \to \{0, 1\}$, Alice receives a point $x \in f^{-1}(1)$, Bob receives $y \in f^{-1}(0)$, and their goal is to find a position $i$ such that $x_i \neq y_i$. Karchmer ... more >>>


TR16-104 | 14th July 2016
Badih Ghazi, Pritish Kamath, Madhu Sudan

Decidability of Non-Interactive Simulation of Joint Distributions

We present decidability results for a sub-class of "non-interactive" simulation problems, a well-studied class of problems in information theory. A non-interactive simulation problem is specified by two distributions $P(x,y)$ and $Q(u,v)$: The goal is to determine if two players, Alice and Bob, that observe sequences $X^n$ and $Y^n$ respectively where ... more >>>


TR19-137 | 24th September 2019
Shachar Lovett, Kewen Wu, Jiapeng Zhang

Decision list compression by mild random restrictions

Revisions: 1

A decision list is an ordered list of rules. Each rule is specified by a term, which is a conjunction of literals, and a value. Given an input, the output of a decision list is the value corresponding to the first rule whole term is satisfied by the input. Decision ... more >>>


TR22-135 | 18th September 2022
Rahul Chugh, Supartha Poddar, Swagato Sanyal

Decision Tree Complexity versus Block Sensitivity and Degree

Comments: 1

Relations between the decision tree complexity and various other complexity measures of Boolean functions is a thriving topic of research in computational complexity. While decision tree complexity is long known to be polynomially related with many other measures, the optimal exponents of many of these relations are not known. It ... more >>>


TR08-020 | 7th March 2008
Irit Dinur, Elena Grigorescu, Swastik Kopparty, Madhu Sudan

Decodability of Group Homomorphisms beyond the Johnson Bound

Given a pair of finite groups $G$ and $H$, the set of homomorphisms from $G$ to $H$ form an error-correcting code where codewords differ in at least $1/2$ the coordinates. We show that for every pair of {\em abelian} groups $G$ and $H$, the resulting code is (locally) list-decodable from ... more >>>


TR19-109 | 21st August 2019
Srikanth Srinivasan, Utkarsh Tripathi, S Venkitesh

Decoding Downset codes over a finite grid

In a recent paper, Kim and Kopparty (Theory of Computing, 2017) gave a deterministic algorithm for the unique decoding problem for polynomials of bounded total degree over a general grid $S_1\times\cdots \times S_m.$ We show that their algorithm can be adapted to solve the unique decoding problem for the general ... more >>>


TR20-179 | 2nd December 2020
Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan

Decoding Multivariate Multiplicity Codes on Product Sets

The multiplicity Schwartz-Zippel lemma bounds the total multiplicity of zeroes of a multivariate polynomial on a product set. This lemma motivates the multiplicity codes of Kopparty, Saraf and Yekhanin [J. ACM, 2014], who showed how to use this lemma to construct high-rate locally-decodable codes. However, the algorithmic results about these ... more >>>


TR16-152 | 27th September 2016
Oded Goldreich

Deconstructing 1-local expanders

Revisions: 1

Contemplating the recently announced 1-local expanders of Viola and Wigderson (ECCC, TR16-129, 2016), one may observe that weaker constructs are well know. For example, one may easily obtain a 4-regular $N$-vertex graph with spectral gap that is $\Omega(1/\log^2 N)$, and similarly a $O(1)$-regular $N$-vertex graph with spectral gap $1/\tildeO(\log N)$.
more >>>


TR14-115 | 27th August 2014
Roei Tell

Deconstructions of Reductions from Communication Complexity to Property Testing using Generalized Parity Decision Trees

Revisions: 1

A few years ago, Blais, Brody, and Matulef (2012) presented a methodology for proving lower bounds for property testing problems by reducing them from problems in communication complexity. Recently, Bhrushundi, Chakraborty, and Kulkarni (2014) showed that some reductions of this type can be deconstructed to two separate reductions, from communication ... more >>>


TR22-159 | 18th November 2022
Songhua He, Periklis Papakonstantinou

Deep Neural Networks: The Missing Complexity Parameter

Deep neural networks are the dominant machine learning model. We show that this model is missing a crucial complexity parameter. Today, the standard neural network (NN) model is a circuit whose gates (neurons) are ReLU units. The complexity of a NN is quantified by the depth (number of layers) and ... more >>>


TR19-044 | 28th March 2019
Eli Ben-Sasson, Lior Goldberg, Swastik Kopparty, Shubhangi Saraf

DEEP-FRI: Sampling Outside the Box Improves Soundness

Revisions: 2

Motivated by the quest for scalable and succinct zero knowledge arguments, we revisit worst-case-to-average-case reductions for linear spaces, raised by [Rothblum, Vadhan, Wigderson, STOC 2013]. The previous state of the art by [Ben-Sasson, Kopparty, Saraf, CCC 2018] showed that if some member of an affine space $U$ is $\delta$-far in ... more >>>


TR03-058 | 22nd July 2003
Vince Grolmusz

Defying Dimensions Modulo 6

Revisions: 2

We show that a certain representation of the matrix-product can be computed with $n^{o(1)}$ multiplications. We also show, that similar representations of matrices can be compressed enormously with the help of simple linear transforms.

more >>>

TR24-015 | 9th January 2024
Harpreet Bedi

Degree 2 lower bound for Permanent in arbitrary characteristic

An elementary proof of quadratic lower bound for determinantal complexity of the permanent in positive characteristic is stated. This is achieved by constructing a sequence of matrices with zero permanent, but the rank of Hessian is bounded below by a degree two polynomial.

more >>>

TR16-069 | 25th April 2016
Parikshit Gopalan, Rocco Servedio, Avishay Tal, Avi Wigderson

Degree and Sensitivity: tails of two distributions

The sensitivity of a Boolean function $f$ is the maximum, over all inputs $x$, of the number of sensitive coordinates of $x$ (namely the number of Hamming neighbors of $x$ with different $f$-value). The well-known sensitivity conjecture of Nisan (see also Nisan and Szegedy) states that every sensitivity-$s$ Boolean function ... more >>>


TR12-015 | 22nd February 2012
Albert Atserias, Anuj Dawar

Degree Lower Bounds of Tower-Type for Approximating Formulas with Parity Quantifiers

Revisions: 2

Kolaitis and Kopparty have shown that for any first-order formula with
parity quantifiers over the language of graphs there is a family of
multi-variate polynomials of constant-degree that agree with the
formula on all but a $2^{-\Omega(n)}$-fraction of the graphs with $n$
vertices. The proof yields a bound on the ... more >>>


TR18-189 | 8th November 2018
Ilias Diakonikolas, Daniel Kane

Degree-$d$ Chow Parameters Robustly Determine Degree-$d$ PTFs (and Algorithmic Applications)

The degree-$d$ Chow parameters of a Boolean function $f: \bn \to \R$ are its degree at most $d$ Fourier coefficients.
It is well-known that degree-$d$ Chow parameters uniquely characterize degree-$d$ polynomial threshold functions
(PTFs)
within the space of all bounded functions. In this paper, we prove a robust ... more >>>


TR17-108 | 19th June 2017
Shafi Goldwasser, Guy Rothblum, Yael Tauman Kalai

Delegating Computation: Interactive Proofs for Muggles

Revisions: 1

In this work we study interactive proofs for tractable languages. The (honest) prover should be efficient and run in polynomial time, or in other words a ``muggle'' (Muggle: ``In the fiction of J.K. Rowling: a person who possesses no magical powers''; from the Oxford English Dictionary). The verifier should be ... more >>>


TR18-161 | 13th September 2018
Justin Holmgren, Ron Rothblum

Delegating Computations with (almost) Minimal Time and Space Overhead

The problem of verifiable delegation of computation considers a setting in which a client wishes to outsource an expensive computation to a powerful, but untrusted, server. Since the client does not trust the server, we would like the server to certify the correctness of the result. Delegation has emerged as ... more >>>


TR11-055 | 14th April 2011
Irit Dinur, Tali Kaufman

Dense locally testable codes cannot have constant rate and distance

A q-query locally testable code (LTC) is an error correcting code that can be tested by a randomized algorithm that reads at most q symbols from the given word.
An important question is whether there exist LTCs that have the ccc property: {c}onstant relative rate, {c}onstant relative distance, and that ... more >>>


TR08-045 | 23rd April 2008
Omer Reingold, Luca Trevisan, Madhur Tulsiani, Salil Vadhan

Dense Subsets of Pseudorandom Sets

A theorem of Green, Tao, and Ziegler can be stated (roughly)
as follows: if R is a pseudorandom set, and D is a dense subset of R,
then D may
be modeled by a set M that is dense in the entire domain such that D and
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 >>>


TR23-061 | 2nd May 2023
Abhimanyu Choudhury, Meena Mahajan

Dependency schemes in CDCL-based QBF solving: a proof-theoretic study

We formalize the notion of proof systems obtained by adding normal dependency schemes into the QCDCL proof system underlying algorithms for solving Quantified Boolean Formulas, by exploring the addition of the dependency schemes via two approaches: one as a preprocessing tool, and second in propagation and learnings in the QCDCL ... more >>>


TR16-028 | 29th February 2016
Olaf Beyersdorff, Joshua Blinkhorn

Dependency Schemes in QBF Calculi:Semantics and Soundness

Revisions: 1

We study the parametrization of QBF resolution calculi by dependency schemes. One of the main problems in this area is to understand for which dependency schemes the resulting calculi are sound. Towards this end we propose a semantic framework for variable independence based on `exhibition' by QBF models, and use ... more >>>


TR15-091 | 3rd June 2015
Joshua Brody, Mario Sanchez

Dependent Random Graphs and Multiparty Pointer Jumping

We initiate a study of a relaxed version of the standard Erdos-Renyi random graph model, where each edge may depend on a few other edges. We call such graphs dependent random graphs. Our main result in this direction is a thorough understanding of the clique number of dependent random graphs. ... more >>>


TR23-121 | 19th August 2023
Theodoros Papamakarios

Depth d Frege systems are not automatable unless P=NP

Revisions: 1

We show that for any integer $d>0$, depth $d$ Frege systems are NP-hard to automate. Namely, given a set $S$ of depth $d$ formulas, it is NP-hard to find a depth $d$ Frege refutation of $S$ in time polynomial in the size of the shortest such a refutation. This extends ... more >>>


TR14-072 | 29th April 2014
Sajin Koroth, Jayalal Sarma

Depth Lower Bounds against Circuits with Sparse Orientation

Revisions: 1

We study depth lower bounds against non-monotone circuits, parametrized by a new measure of non-monotonicity: the orientation of a function $f$ is the characteristic vector of the minimum sized set of negated variables needed in any DeMorgan circuit computing $f$. We prove trade-off results between the depth and the weight/structure ... more >>>


TR21-022 | 20th February 2021
Stefan Dantchev, Nicola Galesi, Abdul Ghani, Barnaby Martin

Depth lower bounds in Stabbing Planes for combinatorial principles

Revisions: 1

We prove logarithmic depth lower bounds in Stabbing Planes for the classes of combinatorial principles known as the Pigeonhole principle and the Tseitin contradictions. The depth lower bounds are new, obtained by giving almost linear length lower bounds which do not depend on the bit-size of the inequalities and in ... more >>>


TR22-087 | 8th June 2022
Pooya Hatami, William Hoza, Avishay Tal, Roei Tell

Depth-$d$ Threshold Circuits vs. Depth-$(d + 1)$ AND-OR Trees

Revisions: 1

For $n \in \mathbb{N}$ and $d = o(\log \log n)$, we prove that there is a Boolean function $F$ on $n$ bits and a value $\gamma = 2^{-\Theta(d)}$ such that $F$ can be computed by a uniform depth-$(d + 1)$ $\text{AC}^0$ circuit with $O(n)$ wires, but $F$ cannot be computed ... more >>>


TR99-023 | 16th June 1999
Amir Shpilka, Avi Wigderson

Depth-3 Arithmetic Formulae over Fields of Characteristic Zero


In this paper we prove near quadratic lower bounds for
depth-3 arithmetic formulae over fields of characteristic zero.
Such bounds are obtained for the elementary symmetric
functions, the (trace of) iterated matrix multiplication, and the
determinant. As corollaries we get the first nontrivial lower
bounds for ... more >>>


TR23-014 | 16th February 2023
Tameem Choudhury, Karteek Sreenivasaiah

Depth-3 Circuit Lower Bounds for k-OV

Revisions: 3

The 2-Orthogonal Vectors (2-OV) problem is the following: given two tuples $A$ and $B$ of $n$ vectors each of dimension $d$, decide if there exists a vector $u\in A$, and $v\in B$ such that $u$ and $v$ are orthogonal. This problem, and its generalization $k$-OV defined analogously for $k$ tuples, ... more >>>


TR23-106 | 17th July 2023
Mika Göös, Ziyi Guan, Tiberiu Mosnoi

Depth-3 Circuits for Inner Product

What is the $\Sigma_3^2$-circuit complexity (depth 3, bottom-fanin 2) of the $2n$-bit inner product function? The complexity is known to be exponential $2^{\alpha_n n}$ for some $\alpha_n=\Omega(1)$. We show that the limiting constant $\alpha=\limsup \alpha_n$ satisfies
\[
0.847... ~\leq~ \alpha ~\leq~ 0.965...\ .
\]
Determining $\alpha$ is one of the ... more >>>


TR15-052 | 6th April 2015
Partha Mukhopadhyay

Depth-4 Identity Testing and Noether's Normalization Lemma

Revisions: 1

We consider the \emph{black-box} polynomial identity testing problem for a sub-class of
depth-4 circuits. Such circuits compute polynomials of the following type:
$
C(x) = \sum_{i=1}^k \prod_{j=1}^{d_i} Q_{i,j},
$
where $k$ is the fan-in of the top $\Sigma$ gate and $r$ is the maximum degree of the ... more >>>


TR20-074 | 6th May 2020
Eric Allender, Archit Chauhan, Samir Datta

Depth-First Search in Directed Graphs, Revisited

Revisions: 3 , Comments: 1

We present an algorithm for constructing a depth-first search tree in planar digraphs; the algorithm can be implemented in the complexity class UL, which is contained in nondeterministic logspace NL, which in turn lies in NC^2. Prior to this (for more than a quarter-century), the fastest uniform deterministic parallel algorithm ... more >>>


TR16-085 | 28th May 2016
Shiteng Chen, Periklis Papakonstantinou

Depth-reduction for composites

We obtain a new depth-reduction construction, which implies a super-exponential improvement in the depth lower bound separating $NEXP$ from non-uniform $ACC$.

In particular, we show that every circuit with $AND,OR,NOT$, and $MOD_m$ gates, $m\in\mathbb{Z}^+$, of polynomial size and depth $d$ can be reduced to a depth-$2$, $SYM\circ AND$, circuit of ... 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 >>>


TR05-114 | 9th October 2005
Boaz Barak, Shien Jin Ong, Salil Vadhan

Derandomization in Cryptography

We give two applications of Nisan--Wigderson-type ("non-cryptographic") pseudorandom generators in cryptography. Specifically, assuming the existence of an appropriate NW-type generator, we construct:

A one-message witness-indistinguishable proof system for every language in NP, based on any trapdoor permutation. This proof system does not assume a shared random string or any ... 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 >>>


TR04-017 | 22nd February 2004
Evgeny Dantsin, Alexander Wolpert

Derandomization of Schuler's Algorithm for SAT

Recently Schuler \cite{Sch03} presented a randomized algorithm that
solves SAT in expected time at most $2^{n(1-1/\log_2(2m))}$ up to a
polynomial factor, where $n$ and $m$ are, respectively, the number of
variables and the number of clauses in the input formula. This bound
is the best known ... 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 >>>


TR22-175 | 16th November 2022
Samuel Epstein

Derandomization Under Different Resource Constraints

Revisions: 1

We provide another proof to the EL Theorem. We show the tradeoff between compressibility of codebooks and their communication capacity. A resource bounded version of the EL Theorem is proven. This is used to prove three instances of resource bounded derandomization.

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-036 | 27th March 2023
Dean Doron, Roei Tell

Derandomization with Minimal Memory Footprint

Existing proofs that deduce BPL=L from circuit lower bounds convert randomized algorithms into deterministic algorithms with large constant overhead in space. We study space-bounded derandomization with minimal footprint, and ask what is the minimal possible space overhead for derandomization.
We show that $BPSPACE[S] \subseteq DSPACE[c \cdot S]$ for $c \approx ... 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 >>>

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


TR10-107 | 6th July 2010
Irit Dinur, Or Meir

Derandomized Parallel Repetition via Structured PCPs

Revisions: 3

A PCP is a proof system for NP in which the proof can be checked by a probabilistic verifier. The verifier is only allowed to read a very small portion of the proof, and in return is allowed to err with some bounded probability. The probability that the verifier accepts ... more >>>


TR05-092 | 23rd August 2005
Eyal Rozenman, Salil Vadhan

Derandomized Squaring of Graphs

We introduce a "derandomized" analogue of graph squaring. This
operation increases the connectivity of the graph (as measured by the
second eigenvalue) almost as well as squaring the graph does, yet only
increases the degree of the graph by a constant factor, instead of
squaring the degree.

One application of ... more >>>


TR23-183 | 24th November 2023
Gil Cohen, Itay Cohen, Gal Maor, Yuval Peled

Derandomized Squaring: An Analytical Insight into Its True Behavior

The notion of the derandomized square of two graphs, denoted as $G \circ H$, was introduced by Rozenman and Vadhan as they rederived Reingold's Theorem, $\mathbf{SL} = \mathbf{L}$. This pseudorandom primitive, closely related to the Zig-Zag product, plays a crucial role in recent advancements on space-bounded derandomization. For this and ... 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 >>>


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


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


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


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


TR24-197 | 29th November 2024
Pranjal Dutta, Amit Sinhababu, Thomas Thierauf

Derandomizing Multivariate Polynomial Factoring for Low Degree Factors

For a polynomial $f$ from a class $\mathcal{C}$ of polynomials, we show that the problem to compute all the constant degree irreducible factors of $f$ reduces in polynomial time to polynomial identity tests (PIT) for class $\mathcal{C}$ and divisibility tests of $f$ by constant degree polynomials. We apply the result ... more >>>


TR13-157 | 11th November 2013
Bin Fu

Derandomizing Polynomial Identity over Finite Fields Implies Super-Polynomial Circuit Lower Bounds for NEXP

Revisions: 1 , Comments: 1

We show that
derandomizing polynomial identity testing over an arbitrary finite
field implies that NEXP does not have polynomial size boolean
circuits. In other words, for any finite field F(q) of size q,
$PIT_q\in NSUBEXP\Rightarrow NEXP\not\subseteq P/poly$, where
$PIT_q$ is the polynomial identity testing problem over F(q), and
NSUBEXP is ... 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 >>>


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


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


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


TR01-087 | 29th October 2001
Bruno Durand, Alexander Shen, Nikolay Vereshchagin

Descriptive complexity of computable sequences

We study different notions of descriptive complexity of
computable sequences. Our main result states that if for almost all
n the Kolmogorov complexity of the n-prefix of an infinite
binary sequence x conditional to n
is less than m then there is a program of length
m^2+O(1) that for ... more >>>


TR11-161 | 4th December 2011
Xin Li

Design Extractors, Non-Malleable Condensers and Privacy Amplification

We introduce a new combinatorial object, called a \emph{design extractor}, that has both the properties of a design and an extractor. We give efficient constructions of such objects and show that they can be used in several applications.

\begin{enumerate}
\item {Improving the output length of known non-malleable extractors.} Non-malleable extractors ... more >>>


TR17-131 | 1st September 2017
Joshua Grochow, Cris Moore

Designing Strassen's algorithm

In 1969, Strassen shocked the world by showing that two n x n matrices could be multiplied in time asymptotically less than $O(n^3)$. While the recursive construction in his algorithm is very clear, the key gain was made by showing that 2 x 2 matrix multiplication could be performed with ... more >>>


TR13-139 | 7th October 2013
Peter Floderus, Andrzej Lingas, Mia Persson, Dzmitry Sledneu

Detecting Monomials with $k$ Distinct Variables

We study the complexity of detecting monomials
with special properties in the sum-product
expansion of a polynomial represented by an arithmetic
circuit of size polynomial in the number of input
variables and using only multiplication and addition.
We focus on monomial properties expressed in terms
of the number of distinct ... more >>>


TR19-042 | 18th March 2019
Ankit Garg, Nikhil Gupta, Neeraj Kayal, Chandan Saha

Determinant equivalence test over finite fields and over $\mathbf{Q}$

The determinant polynomial $Det_n(\mathbf{x})$ of degree $n$ is the determinant of a $n \times n$ matrix of formal variables. A polynomial $f$ is equivalent to $Det_n$ over a field $\mathbf{F}$ if there exists a $A \in GL(n^2,\mathbf{F})$ such that $f = Det_n(A \cdot \mathbf{x})$. Determinant equivalence test over $\mathbf{F}$ is ... more >>>


TR97-036 | 1st August 1997
Meena Mahajan, V Vinay

Determinant: Combinatorics, Algorithms, and Complexity

We prove a new combinatorial characterization of the
determinant. The characterization yields a simple
combinatorial algorithm for computing the
determinant. Hitherto, all (known) algorithms for
determinant have been based on linear algebra. Our
combinatorial algorithm requires no division and works over
arbitrary commutative rings. It also lends itself to
more >>>


TR98-012 | 2nd February 1998
Meena Mahajan, V Vinay

Determinant: Old Algorithms, New Insights


In this paper we approach the problem of computing the characteristic
polynomial of a matrix from the combinatorial viewpoint. We present
several combinatorial characterizations of the coefficients of the
characteristic polynomial, in terms of walks and closed walks of
different kinds in the underlying graph. We develop algorithms based
more >>>


TR23-115 | 8th August 2023
Abhranil Chatterjee, Mrinal Kumar, Ben Lee Volk

Determinants vs. Algebraic Branching Programs

Revisions: 1

We show that for every homogeneous polynomial of degree $d$, if it has determinantal complexity at most $s$, then it can be computed by a homogeneous algebraic branching program (ABP) of size at most $O(d^5s)$. Moreover, we show that for \textit{most} homogeneous polynomials, the width of the resulting homogeneous ABP ... more >>>


TR99-003 | 18th December 1998
Stephen A. Fenner, Frederic Green, Steven Homer, Randall Pruim

Determining Acceptance Possibility for a Quantum Computation is Hard for the Polynomial Hierarchy

It is shown that determining whether a quantum computation
has a non-zero probability of accepting is at least as hard as the
polynomial time hierarchy. This hardness result also applies to
determining in general whether a given quantum basis state appears
with nonzero amplitude in a superposition, or whether a ... more >>>


TR00-003 | 26th November 1999
Matthias Krause, Hans Ulrich Simon

Determining the Optimal Contrast for Secret Sharing Schemes in Visual Cryptography

This paper shows that the largest possible contrast C(k,n)
in a k-out-of-n secret sharing scheme is approximately
4^(-(k-1)). More precisely, we show that
4^(-(k-1)) <= C_{k,n} <= 4^(-(k-1))}n^k/(n(n-1)...(n-(k-1))).
This implies that the largest possible contrast equals
4^(-(k-1)) in the limit when n approaches ... more >>>


TR98-077 | 19th December 1998
Miklos Ajtai

Determinism versus Non-Determinism for Linear Time RAMs with Memory Restrictions

Revisions: 1

Our computational model is a random access machine with $n$
read only input registers each containing $ c \log n$ bits of
information and a read and write memory. We measure the time by the
number of accesses to the input registers. We show that for all $k$
there is ... more >>>


TR11-102 | 31st July 2011
Miklos Ajtai

Determinism Versus Nondeterminism with Arithmetic Tests and Computation

Revisions: 1

For each natural number $d$ we consider a finite structure $M_{d}$ whose
universe is the set of all $0,1$-sequence of length $n=2^{d}$, each
representing a natural number in the set $\lbrace 0,1,...,2^{n}-1\rbrace
$ in binary form.
The operations included in the structure are the
constants $0,1,2^{n}-1,n$, multiplication and addition ... more >>>


TR23-139 | 18th September 2023
Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi

Deterministic Algorithms for Low Degree Factors of Constant Depth Circuits

For every constant $d$, we design a subexponential time deterministic algorithm that takes as input a multivariate polynomial $f$ given as a constant depth algebraic circuit over the field of rational numbers, and outputs all irreducible factors of $f$ of degree at most $d$ together with their respective multiplicities. Moreover, ... more >>>


TR98-072 | 14th December 1998
Ziv Bar-Yossef, Oded Goldreich, Avi Wigderson

Deterministic Amplification of Space Bounded Probabilistic Algorithms.


This paper initiates the study of deterministic amplification of space
bounded probabilistic algorithms. The straightforward implementations of
known amplification methods cannot be used for such algorithms, since they
consume too much space. We present a new implementation of the
Ajtai-Koml\'{o}s-Szemer\'{e}di method, that enables to amplify an $S$ ... more >>>


TR20-137 | 11th September 2020
Zvika Brakerski, Yael Tauman Kalai, Raghuvansh Saxena

Deterministic and Efficient Interactive Coding from Hard-to-Decode Tree Codes

The field of Interactive Coding studies how an interactive protocol can be made resilient to channel errors. Even though this field has received abundant attention since Schulman's seminal paper (FOCS 92), constructing interactive coding schemes that are both deterministic and efficient, and at the same time resilient to adversarial errors ... more >>>


TR13-172 | 1st December 2013
Anindya De, Ilias Diakonikolas, Rocco Servedio

Deterministic Approximate Counting for Degree-$2$ Polynomial Threshold Functions

We give a {\em deterministic} algorithm for approximately computing the fraction of Boolean assignments that satisfy a degree-$2$ polynomial threshold function. Given a degree-2 input polynomial $p(x_1,\dots,x_n)$ and a parameter $\eps > 0$, the algorithm approximates
\[
\Pr_{x \sim \{-1,1\}^n}[p(x) \geq 0]
\]
to within an additive $\pm \eps$ in ... more >>>


TR13-171 | 1st December 2013
Anindya De, Ilias Diakonikolas, Rocco Servedio

Deterministic Approximate Counting for Juntas of Degree-$2$ Polynomial Threshold Functions

Let $g: \{-1,1\}^k \to \{-1,1\}$ be any Boolean function and $q_1,\dots,q_k$ be any degree-2 polynomials over $\{-1,1\}^n.$ We give a \emph{deterministic} algorithm which, given as input explicit descriptions of $g,q_1,\dots,q_k$ and an accuracy parameter $\eps>0$, approximates \[
\Pr_{x \sim \{-1,1\}^n}[g(\sign(q_1(x)),\dots,\sign(q_k(x)))=1] \]
to within an additive $\pm \eps$. For any constant ... 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 >>>


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


TR04-050 | 13th June 2004
Michelle Effros, Leonard Schulman

Deterministic clustering with data nets

We consider the $K$-clustering problem with the $\ell_2^2$
distortion measure, also known as the problem of optimal
fixed-rate vector quantizer design. We provide a deterministic
approximation algorithm which works for all dimensions $d$ and
which, given a data set of size $n$, computes in time
more >>>


TR15-050 | 4th April 2015
Mika Göös, Toniann Pitassi, Thomas Watson

Deterministic Communication vs. Partition Number

Revisions: 1

We show that deterministic communication complexity can be superlogarithmic in the partition number of the associated communication matrix. We also obtain near-optimal deterministic lower bounds for the Clique vs. Independent Set problem, which in particular yields new lower bounds for the log-rank conjecture. All these results follow from a simple ... more >>>


TR12-166 | 25th November 2012
Elad Haramaty, Madhu Sudan

Deterministic Compression with Uncertain Priors

We consider the task of compression of information when the source of the information and the destination do not agree on the prior, i.e., the distribution from which the information is being generated. This setting was considered previously by Kalai et al. (ICS 2011) who suggested that this was a ... more >>>


TR10-162 | 30th October 2010
Zohar Karnin

Deterministic Construction of a high dimensional $\ell_p$ section in $\ell_1^n$ for any $p<2$

For any $00$, we give an efficient
deterministic construction of a linear subspace $V \subseteq
\R^n$, of dimension $(1-\epsilon)n$ in which the $\ell_p$ and
$\ell_r$ norms are the same up to a multiplicative factor of
$\poly(\epsilon^{-1})$ (after the correct normalization). As a
corollary we get a deterministic compressed sensing algorithm
more >>>


TR05-108 | 28th September 2005
Ariel Gabizon, Ran Raz

Deterministic Extractors for Affine Sources over Large Fields

An $(n,k)$-affine source over a finite field $F$ is a random
variable $X=(X_1,...,X_n) \in F^n$, which is uniformly
distributed over an (unknown) $k$-dimensional affine subspace of $
F^n$. We show how to (deterministically) extract practically all
the randomness from affine sources, for any field of size larger
than $n^c$ (where ... more >>>


TR08-042 | 6th April 2008
Zeev Dvir

Deterministic Extractors for Algebraic Sources

An algebraic source is a random variable distributed
uniformly over the set of common zeros of one or more multivariate
polynomials defined over a finite field $F$. Our main result is
the construction of an explicit deterministic extractor for
algebraic sources over exponentially large prime fields. More
precisely, we give ... 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 >>>


TR18-130 | 16th July 2018
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich

Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree

In this paper we study the problem of deterministic factorization of sparse polynomials. We show that if $f \in \mathbb{F}[x_{1},x_{2},\ldots ,x_{n}]$ is a polynomial with $s$ monomials, with individual degrees of its variables bounded by $d$, then $f$ can be deterministically factored in time $s^{\poly(d) \log n}$. Prior to our ... more >>>


TR07-089 | 13th September 2007
Parikshit Gopalan, Venkatesan Guruswami

Deterministic Hardness Amplification via Local GMD Decoding

We study the average-case hardness of the class NP against
deterministic polynomial time algorithms. We prove that there exists
some constant $\mu > 0$ such that if there is some language in NP
for which no deterministic polynomial time algorithm can decide L
correctly on a $1- (log n)^{-\mu}$ fraction ... more >>>


TR14-158 | 26th November 2014
Rohit Gurjar, Arpita Korwar, Nitin Saxena, Thomas Thierauf

Deterministic Identity Testing for Sum of Read Once ABPs

Revisions: 2

A read once ABP is an arithmetic branching program with each variable occurring in at most one layer. We give the first polynomial time whitebox identity test for a polynomial computed by a sum of constantly many ROABPs. We also give a corresponding blackbox algorithm with quasi-polynomial time complexity, i.e. ... 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 >>>


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


TR12-068 | 25th May 2012
Manuel Arora, Gábor Ivanyos, Marek Karpinski, Nitin Saxena

Deterministic Polynomial Factoring and Association Schemes

The problem of finding a nontrivial factor of a polynomial $f(x)$ over a finite field $\mathbb{F}_q$ has many known efficient, but randomized, algorithms. The deterministic complexity of this problem is a famous open question even assuming the generalized Riemann hypothesis (GRH). In this work we improve the state of the ... more >>>


TR09-058 | 4th July 2009
Gábor Ivanyos, Marek Karpinski, Nitin Saxena

Deterministic Polynomial Time Algorithms for Matrix Completion Problems

We present new deterministic algorithms for several cases of the maximum rank matrix completion
problem (for short matrix completion), i.e. the problem of assigning values to the variables in
a given symbolic matrix as to maximize the resulting matrix rank. Matrix completion belongs to
the fundamental problems in computational complexity ... more >>>


TR14-179 | 20th December 2014
Salman Beigi, Omid Etesami, Amin Gohari

Deterministic Randomness Extraction from Generalized and Distributed Santha-Vazirani Sources

A Santha-Vazirani (SV) source is a sequence of random bits where the conditional distribution of each bit, given the previous bits, can be partially controlled by an adversary. Santha and Vazirani show that deterministic randomness extraction from these sources is impossible.
In this paper, we study the generalization of SV ... more >>>


TR96-004 | 18th January 1996
Shiva Chaudhuri, Jaikumar Radhakrishnan

Deterministic Restrictions in Circuit Complexity

We study the complexity of computing Boolean functions using AND, OR
and NOT gates. We show that a circuit of depth $d$ with $S$ gates can
be made to output a constant by setting $O(S^{1-\epsilon(d)})$ (where
$\epsilon(d) = 4^{-d}$) of its input values. This implies a
superlinear size lower bound ... more >>>


TR00-075 | 7th September 2000
Andreas Klein, Martin Kutrib

Deterministic Turing Machines in the Range between Real-Time and Linear-Time

Deterministic k-tape and multitape Turing machines with one-way,
two-way and without a separated input tape are considered. We
investigate the classes of languages acceptable by such devices with
time bounds of the form n+r(n) where r in o(n) is a sublinear
function. It is shown that there ... more >>>


TR13-059 | 9th April 2013
Lior Gishboliner, Asaf Shapira

Deterministic vs Non-deterministic Graph Property Testing

A graph property P is said to be testable if one can check if a graph is close or far from satisfying P using few random local inspections. Property P is said to be non-deterministically testable if one can supply a "certificate" to the fact that a graph satisfies P ... 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 >>>


TR07-124 | 23rd November 2007
Nitin Saxena

Diagonal Circuit Identity Testing and Lower Bounds

In this paper we give the first deterministic polynomial time algorithm for testing whether a {\em diagonal} depth-$3$ circuit $C(\arg{x}{n})$ (i.e. $C$ is a sum of powers of linear functions) is zero. We also prove an exponential lower bound showing that such a circuit will compute determinant or permanent only ... more >>>


TR23-002 | 5th January 2023
Noga Alon, Olivier Bousquet, Kasper Green Larsen, Shay Moran, Shlomo Moran

Diagonalization Games

Revisions: 2

We study several variants of a combinatorial game which is based on Cantor's diagonal argument. The game is between two players called Kronecker and Cantor. The names of the players are motivated by the known fact that Leopold Kronecker did not appreciate Georg Cantor's arguments about the infinite, and even ... more >>>


TR04-018 | 24th January 2004
Jan Krajicek

Diagonalization in proof complexity

We study the diagonalization in the context of proof
complexity. We prove that at least one of the
following three conjectures is true:

1. There is a boolean function computable in E
that has circuit complexity $2^{\Omega(n)}$.

2. NP is not closed under the complement.

3. There is no ... more >>>


TR22-059 | 27th April 2022
Siddhesh Chaubal, Anna Gal

Diameter versus Certificate Complexity of Boolean Functions

In this paper, we introduce a measure of Boolean functions we call diameter, that captures the relationship between certificate complexity and several other measures of Boolean functions. Our measure can be viewed as a variation on alternating number, but while alternating number can be exponentially larger than certificate complexity, we ... more >>>


TR04-091 | 29th September 2004
Ondrej Klíma, Pascal Tesson, Denis Thérien

Dichotomies in the Complexity of Solving Systems of Equations over Finite Semigroups

We consider the problem of testing whether a given system of equations
over a fixed finite semigroup S has a solution. For the case where
S is a monoid, we prove that the problem is computable in polynomial
time when S is commutative and is the union of its subgroups
more >>>


TR15-084 | 21st May 2015
Or Ordentlich, Ofer Shayevitz, Omri Weinstein

Dictatorship is the Most Informative Balanced Function at the Extremes

Revisions: 2

Suppose $X$ is a uniformly distributed $n$-dimensional binary vector and $Y$ is obtained by passing $X$ through a binary symmetric channel with crossover probability $\alpha$. A recent conjecture by Courtade and Kumar postulates that $I(f(X);Y)\leq 1-h(\alpha)$ for any Boolean function $f$. In this paper, we prove the conjecture for all ... 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 >>>


TR14-162 | 28th November 2014
Michael Forbes, Venkatesan Guruswami

Dimension Expanders via Rank Condensers

An emerging theory of "linear-algebraic pseudorandomness" aims to understand the linear-algebraic analogs of fundamental Boolean pseudorandom objects where the rank of subspaces plays the role of the size of subsets. In this work, we study and highlight the interrelationships between several such algebraic objects such as subspace designs, dimension ... more >>>


TR06-080 | 16th June 2006
David Doty

Dimension Extractors

A dimension extractor is an algorithm designed to increase the effective dimension -- i.e., the computational information density -- of an infinite sequence. A constructive dimension extractor is exhibited by showing that every sequence of positive constructive dimension is Turing equivalent to a sequence of constructive strong dimension arbitrarily ... more >>>


TR04-104 | 19th November 2004
Maria Lopez-Valdes, Mayordomo Elvira

Dimension is compression

Effective fractal dimension was defined by Lutz (2003) in order to quantitatively analyze the structure of complexity classes.
Interesting connections of effective dimension with information theory were also found, in fact the cases of polynomial-space and constructive dimension can be precisely characterized in terms of Kolmogorov complexity, while analogous ... more >>>


TR17-125 | 7th August 2017
Badih Ghazi, Pritish Kamath, Prasad Raghavendra

Dimension Reduction for Polynomials over Gaussian Space and Applications

In this work we introduce a new technique for reducing the dimension of the ambient space of low-degree polynomials in the Gaussian space while preserving their relative correlation structure. As applications, we address the following problems:

(I) Computability of the Approximately Optimal Noise Stable function over Gaussian space:

The goal ... more >>>


TR21-066 | 5th May 2021
Lianna Hambardzumyan, Hamed Hatami, Pooya Hatami

Dimension-free Bounds and Structural Results in Communication Complexity

The purpose of this article is to initiate a systematic study of dimension-free relations between basic communication and query complexity measures and various matrix norms. In other words, our goal is to obtain inequalities that bound a parameter solely as a function of another parameter. This is in contrast to ... more >>>


TR05-089 | 30th July 2005
Xiaoyang Gu, Jack H. Lutz, Philippe Moser

Dimensions of Copeland-Erdos Sequences

The base-$k$ {\em Copeland-Erd\"os sequence} given by an infinite
set $A$ of positive integers is the infinite
sequence $\CE_k(A)$ formed by concatenating the base-$k$
representations of the elements of $A$ in numerical
order. This paper concerns the following four
quantities.
\begin{enumerate}[$\bullet$]
\item
The {\em finite-state dimension} $\dimfs (\CE_k(A))$,
a finite-state ... more >>>


TR13-179 | 15th December 2013
Irit Dinur, David Steurer

Direct Product Testing


A direct product is a function of the form $g(x_1,\ldots,x_k)=(g_1(x_1),\ldots,g_k(x_k))$. We show that the direct product property is locally testable with $2$ queries, that is, a canonical two-query test distinguishes between direct products and functions that are from direct products with constant probability.

This local testing question comes up ... more >>>


TR14-182 | 22nd December 2014
Dana Moshkovitz

Direct Product Testing With Nearly Identical Sets

Comments: 1

In this work we analyze a direct product test in which each of two provers receives a subset of size n of a ground set U,
and the two subsets intersect in about (1-\delta)n elements.
We show that if each of the provers provides labels to the n ... more >>>


TR07-064 | 19th June 2007
Rahul Jain, Hartmut Klauck, Ashwin Nayak

Direct Product Theorems for Communication Complexity via Subdistribution Bounds

A basic question in complexity theory is whether the computational
resources required for solving k independent instances of the same
problem scale as k times the resources required for one instance.
We investigate this question in various models of classical
communication complexity.

We define a new measure, the subdistribution bound, ... more >>>


TR13-035 | 6th March 2013
Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff

Direct product via round-preserving compression

Revisions: 1

We obtain a strong direct product theorem for two-party bounded round communication complexity.
Let suc_r(\mu,f,C) denote the maximum success probability of an r-round communication protocol that uses
at most C bits of communication in computing f(x,y) when (x,y)~\mu.
Jain et al. [JPY12] have recently showed that if
more >>>


TR12-143 | 5th November 2012
Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff

Direct Products in Communication Complexity

Revisions: 2

We give exponentially small upper bounds on the success probability for computing the direct product of any function over any distribution using a communication protocol. Let suc(?,f,C) denote the maximum success probability of a 2-party communication protocol for computing f(x,y) with C bits of communication, when the inputs (x,y) are ... more >>>


TR22-114 | 16th August 2022
Hao Wu

Direct Sum Theorems From Fortification

Revisions: 1

We revisit the direct sum theorems in communication complexity which askes whether the resource to solve $n$ communication problems together is (approximately) the sum of resources to solve these problems separately. Our work starts with the observation that Meir and Dinur's fortification lemma for protocol size over rectangles can be ... more >>>


TR20-164 | 9th November 2020
Andrej Bogdanov, Gautam Prakriya

Direct Sum and Partitionability Testing over General Groups

Revisions: 1

A function $f(x_1, \dots, x_n)$ from a product domain $\mathcal{D}_1 \times \cdots \times \mathcal{D}_n$ to an abelian group $\mathcal{G}$ is a direct sum if it is of the form $f_1(x_1) + \cdots + f_n(x_n)$. We present a new 4-query direct sum test with optimal (up to constant factors) soundness error. ... more >>>


TR13-079 | 2nd June 2013
Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff

Direct Sum Fails for Zero Error Average Communication

We show that in the model of zero error communication complexity, direct sum fails for average communication complexity as well as for external information cost. Our example also refutes a version of a conjecture by Braverman et al. that in the zero error case amortized communication complexity equals external information ... more >>>


TR14-002 | 8th January 2014
Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, Igor Shinkar

Direct Sum Testing

Revisions: 1

For a string $a \in \{0,1\}^n$ its $k$-fold direct sum encoding is a function $f_a$ that takes as input sets $S \subseteq [n]$ of
size $k$ and outputs $f_a(S) = \sum_{i \in S} a_i$.
In this paper we are interested in the Direct Sum Testing Problem,
where we are given ... more >>>


TR19-139 | 8th October 2019
Irit Dinur, Konstantin Golubev

Direct sum testing - the general case


A function f:[n_1] x ... x [n_d]-->F is a direct sum if it is of the form f(a_1,...,a_d) = f_1(a_1) + ... + f_d (a_d) (mod 2) for some d functions f_i:[n_i]-->F_i for all i=1,...,d. We present a 4-query test which distinguishes between direct sums and functions that are ... more >>>


TR09-044 | 6th May 2009
Boaz Barak, Mark Braverman, Xi Chen, Anup Rao

Direct Sums in Randomized Communication Complexity

Does computing n copies of a function require n times the computational effort? In this work, we

give the first non-trivial answer to this question for the model of randomized communication

complexity.

We show that:

1. Computing n copies of a function requires sqrt{n} times the ... more >>>


TR22-162 | 10th November 2022
Hadley Black, Deeparnab Chakrabarty, C. Seshadhri

Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an $\widetilde{O}(n\sqrt{d})$ Monotonicity Tester

The problem of testing monotonicity for Boolean functions on the hypergrid, $f:[n]^d \to \{0,1\}$ is a classic topic in property testing. When $n=2$, the domain is the hypercube. For the hypercube case, a breakthrough result of Khot-Minzer-Safra (FOCS 2015) gave a non-adaptive, one-sided tester making $\widetilde{O}(\varepsilon^{-2}\sqrt{d})$ queries. Up to polylog ... more >>>


TR24-087 | 27th April 2024
Renato Ferreira Pinto Jr.

Directed Isoperimetry and Monotonicity Testing: A Dynamical Approach

Revisions: 1

This paper explores the connection between classical isoperimetric inequalities, their directed analogues, and monotonicity testing. We study the setting of real-valued functions $f : [0,1]^d \to \mathbb{R}$ on the solid unit cube, where the goal is to test with respect to the $L^p$ distance. Our goals are twofold: to further ... more >>>


TR23-101 | 5th July 2023
Renato Ferreira Pinto Jr.

Directed Poincaré Inequalities and $L^1$ Monotonicity Testing of Lipschitz Functions

We study the connection between directed isoperimetric inequalities and monotonicity testing. In recent years, this connection has unlocked breakthroughs for testing monotonicity of functions defined on discrete domains. Inspired the rich history of isoperimetric inequalities in continuous settings, we propose that studying the relationship between directed isoperimetry and monotonicity in ... more >>>


TR17-153 | 9th October 2017
Pranjal Dutta, Nitin Saxena, Amit Sinhababu

Discovering the roots: Uniform closure results for algebraic classes under factoring

Newton iteration (NI) is an almost 350 years old recursive formula that approximates a simple root of a polynomial quite rapidly. We generalize it to a matrix recurrence (allRootsNI) that approximates all the roots simultaneously. In this form, the process yields a better circuit complexity in the case when the ... more >>>


TR07-050 | 25th May 2007
Arkadev Chattopadhyay

Discrepancy and the power of bottom fan-in in depth-three circuits

We develop a new technique of proving lower bounds for the randomized communication complexity of boolean functions in the multiparty 'Number on the Forehead' model. Our method is based on the notion of voting polynomial degree of functions and extends the Degree-Discrepancy Lemma in the recent work of Sherstov (STOC'07). ... more >>>


TR16-108 | 16th July 2016
Michael Rudow

Discrete Logarithm and Minimum Circuit Size

This paper shows that the Discrete Logarithm Problem is in ZPP^(MCSP) (where MCSP is the Minimum Circuit Size Problem). This result improves the previous bound that the Discrete Logarithm Problem is in BPP^(MCSP) Allender et al. (2006). In doing so, this paper helps classify the relative difficulty of the Minimum ... more >>>


TR03-011 | 17th February 2003
Christian Glaßer, Alan L. Selman, Samik Sengupta, Liyu Zhang

Disjoint NP-Pairs

We study the question of whether the class DisNP of
disjoint pairs (A, B) of NP-sets contains a complete pair.
The question relates to the question of whether optimal
proof systems exist, and we relate it to the previously
studied question of whether there exists ... more >>>


TR05-083 | 24th July 2005
Olaf Beyersdorff

Disjoint NP-Pairs from Propositional Proof Systems

For a proof system P we introduce the complexity class DNPP(P)
of all disjoint NP-pairs for which the disjointness of the pair is
efficiently provable in the proof system P.
We exhibit structural properties of proof systems which make the
previously defined canonical NP-pairs of these proof systems hard ... more >>>


TR08-003 | 25th December 2007
Troy Lee, Adi Shraibman

Disjointness is hard in the multi-party number-on-the-forehead model

We show that disjointness requires randomized communication
Omega(\frac{n^{1/2k}}{(k-1)2^{k-1}2^{2^{k-1}}})
in the general k-party number-on-the-forehead model of complexity.
The previous best lower bound was Omega(\frac{log n}{k-1}). By
results of Beame, Pitassi, and Segerlind, this implies
2^{n^{Omega(1)}} lower bounds on the size of tree-like Lovasz-Schrijver
proof systems needed to refute certain unsatisfiable ... more >>>


TR20-114 | 22nd July 2020
Anup Bhattacharya, Sourav Chakraborty, Arijit Ghosh, Gopinath Mishra, Manaswi Paraashar

Disjointness through the Lens of Vapnik–Chervonenkis Dimension: Sparsity and Beyond

The disjointness problem - where Alice and Bob are given two subsets of $\{1, \dots, n\}$ and they have to check if their sets intersect - is a central problem in the world of communication complexity. While both deterministic and randomized communication complexities for this problem are known to be ... more >>>


TR11-127 | 18th September 2011
Ronen Shaltiel

Dispersers for affine sources with sub-polynomial entropy

We construct an explicit disperser for affine sources over $\F_2^n$ with entropy $k=2^{\log^{0.9} n}=n^{o(1)}$. This is a polynomial time computable function $D:\F_2^n \ar \B$ such that for every affine space $V$ of $\F_2^n$ that has dimension at least $k$, $D(V)=\set{0,1}$. This improves the best previous construction of Ben-Sasson and Kopparty ... more >>>


TR06-102 | 15th August 2006
Luis Rademacher, Santosh Vempala

Dispersion of Mass and the Complexity of Randomized Geometric Algorithms

How much can randomness help computation? Motivated by this general question and by volume computation, one of the few instances where randomness provably helps, we analyze a notion of dispersion and connect it to asymptotic convex geometry. We obtain a nearly quadratic lower bound on the complexity of randomized volume ... more >>>


TR05-021 | 14th February 2005
Stasys Jukna

Disproving the single level conjecture

Revisions: 2 , Comments: 1

We consider the minimal number of AND and OR gates in monotone
circuits for quadratic boolean functions, i.e. disjunctions of
length-$2$ monomials. The single level conjecture claims that
monotone single level circuits, i.e. circuits which have only one
level of AND gates, for quadratic functions ... more >>>


TR10-119 | 27th July 2010
Michal Moshkovitz

Distance Estimators with Sublogarithmic Number of Queries

A distance estimator is a code together with a randomized algorithm. The algorithm approximates the distance of any word from the code by making a small number of queries to the word. One such example is the Reed-Muller code equipped with an appropriate algorithm. It has polynomial length, polylogarithmic alphabet ... more >>>


TR24-139 | 11th September 2024
Jiatu Li, Edward Pyne, Roei Tell

Distinguishing, Predicting, and Certifying: On the Long Reach of Partial Notions of Pseudorandomness

This paper revisits the study of two classical technical tools in theoretical computer science: Yao's transformation of distinguishers to next-bit predictors (FOCS 1982), and the ``reconstruction paradigm'' in pseudorandomness (e.g., as in Nisan and Wigderson, JCSS 1994). Recent works of Pyne, Raz, and Zhan (FOCS 2023) and Doron, Pyne, and ... more >>>


TR18-079 | 19th April 2018
Jayadev Acharya, Clement Canonne, Himanshu Tyagi

Distributed Simulation and Distributed Inference

Revisions: 1

Independent samples from an unknown probability distribution $\mathbf{p}$ on a domain of size $k$ are distributed across $n$ players, with each player holding one sample. Each player can communicate $\ell$ bits to a central referee in a simultaneous message passing (SMP) model of communication to help the referee infer a ... more >>>


TR11-089 | 7th June 2011
Paul Valiant

Distribution Free Evolvability of Polynomial Functions over all Convex Loss Functions

Revisions: 1

We formulate a notion of evolvability for functions with domain and range that are real-valued vectors, a compelling way of expressing many natural biological processes. We show that linear and fixed degree polynomial functions are evolvable in the following dually robust sense: There is a single evolution algorithm that for ... more >>>


TR23-118 | 17th August 2023
Hugo Aaronson, Tom Gur, Ninad Rajgopal, Ron Rothblum

Distribution-Free Proofs of Proximity

Revisions: 2

Motivated by the fact that input distributions are often unknown in advance, distribution-free property testing considers a setting in which the algorithmic task is to accept functions $f : [n] \to \{0,1\}$ having a certain property $\Pi$ and reject functions that are $\varepsilon$-far from $\Pi$, where the distance is measured ... more >>>


TR12-186 | 27th December 2012
Andreas Krebs, Nutan Limaye

DLOGTIME-Proof Systems

We define DLOGTIME proof systems, DLTPS, which generalize NC0 proof systems.
It is known that functions such as Exact-k and Majority do not have NC0 proof systems. Here, we give a DLTPS for Exact-k (and therefore for Majority) and also for other natural functions such as Reach and k-Clique. Though ... more >>>


TR12-060 | 16th May 2012
Parikshit Gopalan, Raghu Meka, Omer Reingold

DNF Sparsification and a Faster Deterministic Counting

Revisions: 2

Given a DNF formula $f$ on $n$ variables, the two natural size measures are the number of terms or size $s(f)$, and the maximum width of a term $w(f)$. It is folklore that short DNF formulas can be made narrow. We prove a converse, showing that narrow formulas can be ... more >>>


TR18-190 | 5th November 2018
Shachar Lovett, Jiapeng Zhang

DNF sparsification beyond sunflowers

There are two natural complexity measures associated with DNFs: their size, which is the number of clauses; and their width, which is the maximal number of variables in a clause. It is a folklore result that DNFs of small size can be approximated by DNFs of small width (logarithmic in ... more >>>


TR05-075 | 4th July 2005
Martin Dyer, Leslie Ann Goldberg, Mark Jerrum

Dobrushin conditions and Systematic Scan

Revisions: 1

We consider Glauber dynamics on finite spin systems.
The mixing time of Glauber dynamics can be bounded
in terms of the influences of sites on each other.
We consider three parameters bounding these influences ---
$\alpha$, the total influence on a site, as studied by Dobrushin;
$\alpha'$, the total influence ... more >>>


TR17-109 | 22nd June 2017
Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, Shadab Romani

Does Looking Inside a Circuit Help?

The Black-Box Hypothesis, introduced by Barak et al. (JACM, 2012), states that any property of boolean functions decided efficiently (e.g., in BPP) with inputs represented by circuits can also be decided efficiently in the black-box setting, where an algorithm is given an oracle access to the input function and an ... more >>>


TR23-207 | 13th December 2023
Omri Ben-Eliezer, Tomer Grossman, Moni Naor

Does Prior Knowledge Help Detect Collisions?

Suppose you are given a function $f\colon [n] \to [n]$ via (black-box) query access to the function. You are looking to find something local, like a collision (a pair $x \neq y$ s.t.\ $f(x)=f(y)$). The question is whether knowing the `shape' of the function helps you or not (by shape ... more >>>


TR06-114 | 22nd August 2006
Carl Bosley, Yevgeniy Dodis

Does Privacy Require True Randomness?

Most cryptographic primitives require randomness (for example, to generate their secret keys). Usually, one assumes that perfect randomness is available, but, conceivably, such primitives might be built under weaker, more realistic assumptions. This is known to be true for many authentication applications, when entropy alone is typically sufficient. In contrast, ... more >>>


TR21-104 | 26th June 2021
Sravanthi Chede, Anil Shukla

Does QRAT simulate IR-calc? QRAT simulation algorithm for $\forall$Exp+Res cannot be lifted to IR-calc

We show that the QRAT simulation algorithm of $\forall$Exp+Res from [B. Kiesl and M. Seidl, 2019] cannot be lifted to IR-calc.

more >>>

TR17-069 | 17th April 2017
Jacob Steinhardt

Does robustness imply tractability? A lower bound for planted clique in the semi-random model

We consider a robust analog of the planted clique problem. In this analog, a set $S$ of vertices is chosen and all edges in $S$ are included; then, edges between $S$ and the rest of the graph are included with probability $\frac{1}{2}$, while edges not touching $S$ are allowed to ... more >>>


TR19-098 | 20th July 2019
Jayadev Acharya, Clement Canonne, Yanjun Han, Ziteng Sun, Himanshu Tyagi

Domain Compression and its Application to Randomness-Optimal Distributed Goodness-of-Fit

We study goodness-of-fit of discrete distributions in the distributed setting, where samples are divided between multiple users who can only release a limited amount of information about their samples due to various information constraints. Recently, a subset of the authors showed that having access to a common random seed (i.e., ... more >>>


TR18-187 | 4th November 2018
Hadley Black, Deeparnab Chakrabarty, C. Seshadhri

Domain Reduction for Monotonicity Testing: A $o(d)$ Tester for Boolean Functions on Hypergrids

Revisions: 4

Testing monotonicity of Boolean functions over the hypergrid, $f:[n]^d \to \{0,1\}$, is a classic problem in property testing. When the range is real-valued, there are $\Theta(d\log n)$-query testers and this is tight. In contrast, the Boolean range qualitatively differs in two ways:
(1) Independence of $n$: There are testers ... more >>>


TR24-114 | 12th July 2024
Nir Bitansky, Ron D. Rothblum, Prahladh Harsha, Yuval Ishai, David Wu

Dot-Product Proofs and Their Applications

A dot-product proof (DPP) is a simple probabilistic proof system in which the input statement $x$ and the proof ${\pi}$ are vectors over a finite field $\mathbb{F}$, and the proof is verified by making a single dot-product query $\langle {q},({x} \| {\pi})\rangle$ jointly to ${x}$ and ${\pi}$. A DPP can ... more >>>


TR16-016 | 30th January 2016
Zi-Wen Liu, Christopher Perry, Yechao Zhu, Dax Enshan Koh, Scott Aaronson

Doubly infinite separation of quantum information and communication

We prove the existence of (one-way) communication tasks with a subconstant versus superconstant asymptotic gap, which we call "doubly infinite," between their quantum information and communication complexities. We do so by studying the exclusion game [C. Perry et al., Phys. Rev. Lett. 115, 030504 (2015)] for which there exist instances ... more >>>


TR23-161 | 1st November 2023
Tal Herman, Guy Rothblum

Doubly-Efficient Interactive Proofs for Distribution Properties

Revisions: 1

Suppose we have access to a small number of samples from an unknown distribution, and would like learn facts about the distribution.
An untrusted data server claims to have studied the distribution and makes assertions about its properties. Can the untrusted data server prove that its assertions are approximately correct? ... more >>>


TR24-101 | 21st May 2024
Or Keret, Ron Rothblum, Prashant Nalini Vasudevan

Doubly-Efficient Batch Verification in Statistical Zero-Knowledge

A sequence of recent works, concluding with Mu et al. (Eurocrypt, 2024) has shown that every problem $\Pi$ admitting a non-interactive statistical zero-knowledge proof (NISZK) has an efficient zero-knowledge batch verification protocol. Namely, an NISZK protocol for proving that $x_1,\dots,x_k \in \Pi$ with communication that only scales poly-logarithmically with $k$. ... more >>>


TR19-135 | 2nd October 2019
Michel Goemans, Shafi Goldwasser, Dhiraj Holden

Doubly-Efficient Pseudo-Deterministic Proofs

In [20] Goldwasser, Grossman and Holden introduced pseudo-deterministic interactive proofs for search problems where a powerful prover can convince a probabilistic polynomial time verifier that a solution to a search problem is canonical. They studied search problems for which polynomial time algorithms are not known and for which many solutions ... more >>>


TR22-133 | 20th September 2022
Prahladh Harsha, Daniel Mitropolsky, Alon Rosen

Downward Self-Reducibility in TFNP

Revisions: 1 , Comments: 1

A problem is downward self-reducible if it can be solved efficiently given an oracle that returns
solutions for strictly smaller instances. In the decisional landscape, downward self-reducibility is
well studied and it is known that all downward self-reducible problems are in PSPACE. In this
paper, we initiate the study of ... more >>>


TR03-003 | 19th December 2002
Fahiem Bacchus, Shannon Dalmao

DPLL with Caching: A new algorithm for #SAT and Bayesian Inference

Bayesian inference and counting satisfying assignments are important
problems with numerous applications in probabilistic reasoning. In this
paper, we show that plain old DPLL equipped with memoization can solve
both of these problems with time complexity that is at least as
good as all known algorithms. Furthermore, DPLL with memoization
more >>>


TR13-032 | 26th February 2013
Mark Bun, Justin Thaler

Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities

Revisions: 2

The $\epsilon$-approximate degree of a Boolean function $f: \{-1, 1\}^n \to \{-1, 1\}$ is the minimum degree of a real polynomial that approximates $f$ to within $\epsilon$ in the $\ell_\infty$ norm. We prove several lower bounds on this important complexity measure by explicitly constructing solutions to the dual of an ... more >>>


TR17-062 | 9th April 2017
Arkadev Chattopadhyay, Nikhil Mande

Dual polynomials and communication complexity of XOR functions

We show a new duality between the polynomial margin complexity of $f$ and the discrepancy of the function $f \circ$ XOR, called an XOR function. Using this duality,
we develop polynomial based techniques for understanding the bounded error (BPP) and the weakly-unbounded error (PP) communication complexities of XOR functions. ... more >>>


TR15-041 | 25th March 2015
Mark Bun, Justin Thaler

Dual Polynomials for Collision and Element Distinctness

The approximate degree of a Boolean function $f: \{-1, 1\}^n \to \{-1, 1\}$ is the minimum degree of a real polynomial that approximates $f$ to within error $1/3$ in the $\ell_\infty$ norm. In an influential result, Aaronson and Shi (J. ACM 2004) proved tight $\tilde{\Omega}(n^{1/3})$ and $\tilde{\Omega}(n^{2/3})$ lower bounds on ... more >>>


TR14-122 | 30th September 2014
Eric Allender, Anna Gal, Ian Mertz

Dual VP Classes

Revisions: 2

We consider arithmetic complexity classes that are in some sense dual to the classes VP(Fp) that were introduced by Valiant. This provides new characterizations of the complexity classes ACC^1 and TC^1, and also provides a compelling example of
a class of high-degree polynomials that can be simulated via arithmetic circuits ... more >>>


TR95-020 | 8th March 1995
William Hurwood

Dynamic Fault Diagnosis

We consider a dynamic fault diagnosis problem: There are n
processors, to be tested in a series of rounds. In every
testing round we use a directed matching to have some
processors report on the status (good or faulty) of other
processors. Also in each round ... more >>>


TR19-146 | 31st October 2019
Max Bannach, Zacharias Heinrich, Rüdiger Reischuk, Till Tantau

Dynamic Kernels for Hitting Sets and Set Packing

Computing kernels for the hitting set problem (the problem of
finding a size-$k$ set that intersects each hyperedge of a
hypergraph) is a well-studied computational problem. For hypergraphs
with $m$ hyperedges, each of size at most~$d$, the best algorithms
can compute kernels of size $O(k^d)$ in ... more >>>


TR01-090 | 28th November 2001
Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk

Dynamic Process Graphs and the Complexity of Scheduling

In parallel and distributed computing scheduling low level tasks
on the available hardware is a fundamental problem.
Traditionally, one has assumed that the set of tasks to be executed
is known beforehand.
Then the scheduling constraints are given by a precedence graph.
Nodes represent the elementary tasks ... more >>>




ISSN 1433-8092 | Imprint