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

__
TR16-104
| 14th July 2016
__

Badih Ghazi, Pritish Kamath, Madhu Sudan#### Decidability of Non-Interactive Simulation of Joint Distributions

__
TR08-020
| 7th March 2008
__

Irit Dinur, Elena Grigorescu, Swastik Kopparty, Madhu Sudan#### Decodability of Group Homomorphisms beyond the Johnson Bound

__
TR16-152
| 27th September 2016
__

Oded Goldreich#### Deconstructing 1-local expanders

Revisions: 1

__
TR14-115
| 27th August 2014
__

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

Revisions: 1

__
TR03-058
| 22nd July 2003
__

Vince Grolmusz#### Defying Dimensions Modulo 6

Revisions: 2

__
TR16-069
| 25th April 2016
__

Parikshit Gopalan, Rocco Servedio, Avishay Tal, Avi Wigderson#### Degree and Sensitivity: tails of two distributions

__
TR12-015
| 22nd February 2012
__

Albert Atserias, Anuj Dawar#### Degree Lower Bounds of Tower-Type for Approximating Formulas with Parity Quantifiers

Revisions: 2

__
TR17-108
| 19th June 2017
__

Shafi Goldwasser, Guy Rothblum, Yael Tauman Kalai#### Delegating Computation: Interactive Proofs for Muggles

Revisions: 1

__
TR11-055
| 14th April 2011
__

Irit Dinur, Tali Kaufman#### Dense locally testable codes cannot have constant rate and distance

__
TR08-045
| 23rd April 2008
__

Omer Reingold, Luca Trevisan, Madhur Tulsiani, Salil Vadhan#### Dense Subsets of Pseudorandom Sets

__
TR15-006
| 6th January 2015
__

Nader Bshouty#### Dense Testers: Almost Linear Time and Locally Explicit Constructions

__
TR16-028
| 29th February 2016
__

Olaf Beyersdorff, Joshua Blinkhorn#### Dependency Schemes in QBF Calculi:Semantics and Soundness

Revisions: 1

__
TR15-091
| 3rd June 2015
__

Joshua Brody, Mario Sanchez#### Dependent Random Graphs and Multiparty Pointer Jumping

__
TR14-072
| 29th April 2014
__

Sajin Koroth, Jayalal Sarma#### Depth Lower Bounds against Circuits with Sparse Orientation

Revisions: 1

__
TR99-023
| 16th June 1999
__

Amir Shpilka, Avi Wigderson#### Depth-3 Arithmetic Formulae over Fields of Characteristic Zero

__
TR15-052
| 6th April 2015
__

Partha Mukhopadhyay#### Depth-4 Identity Testing and Noether's Normalization Lemma

Revisions: 1

__
TR16-085
| 28th May 2016
__

Shiteng Chen, Periklis Papakonstantinou#### Depth-reduction for composites

__
TR05-114
| 9th October 2005
__

Boaz Barak, Shien Jin Ong, Salil Vadhan#### Derandomization in Cryptography

__
TR05-027
| 19th February 2005
__

Daniel Rolf#### Derandomization of PPSZ for Unique-$k$-SAT

__
TR04-017
| 22nd February 2004
__

Evgeny Dantsin, Alexander Wolpert#### Derandomization of Schuler's Algorithm for SAT

__
TR02-039
| 30th June 2002
__

Oded Goldreich, Avi Wigderson#### Derandomization that is rarely wrong from short advice that is typically good

Comments: 1

__
TR02-008
| 11th January 2002
__

Valentine Kabanets#### Derandomization: A Brief Overview

__
TR06-002
| 4th January 2006
__

Eyal Kaplan, Moni Naor, Omer Reingold#### Derandomized Constructions of k-Wise (Almost) Independent Permutations

__
TR10-107
| 6th July 2010
__

Irit Dinur, Or Meir#### Derandomized Parallel Repetition via Structured PCPs

Revisions: 3

__
TR05-092
| 23rd August 2005
__

Eyal Rozenman, Salil Vadhan#### Derandomized Squaring of Graphs

__
TR09-146
| 29th December 2009
__

Dan Gutfreund, Akinori Kawachi#### Derandomizing Arthur-Merlin Games and Approximate Counting Implies Exponential-Size Lower Bounds

__
TR16-083
| 23rd May 2016
__

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

__
TR18-051
| 15th March 2018
__

Stasys Jukna#### Derandomizing Dynamic Programming and Beyond

__
TR17-052
| 19th March 2017
__

Dieter van Melkebeek, Gautam Prakriya#### Derandomizing Isolation in Space-Bounded Settings

__
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

__
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

__
TR10-188
| 8th December 2010
__

Matthew Anderson, Dieter van Melkebeek, Ilya Volkovich#### Derandomizing Polynomial Identity Testing for Multilinear Constant-Read Formulae

Revisions: 1

__
TR02-055
| 13th September 2002
__

Valentine Kabanets, Russell Impagliazzo#### Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds

Revisions: 1

__
TR06-105
| 23rd August 2006
__

Avi Wigderson, David Xiao#### Derandomizing the AW matrix-valued Chernoff bound using pessimistic estimators and applications

__
TR08-049
| 10th April 2008
__

Vikraman Arvind, Partha Mukhopadhyay#### Derandomizing the Isolation Lemma and Lower Bounds for Noncommutative Circuit Size

Revisions: 3

__
TR01-087
| 29th October 2001
__

Bruno Durand, Alexander Shen, Nikolay Vereshchagin#### Descriptive complexity of computable sequences

__
TR11-161
| 4th December 2011
__

Xin Li#### Design Extractors, Non-Malleable Condensers and Privacy Amplification

__
TR17-131
| 1st September 2017
__

Joshua Grochow, Cris Moore#### Designing Strassen's algorithm

__
TR13-139
| 7th October 2013
__

Peter Floderus, Andrzej Lingas, Mia Persson, Dzmitry Sledneu#### Detecting Monomials with $k$ Distinct Variables

__
TR97-036
| 1st August 1997
__

Meena Mahajan, V Vinay#### Determinant: Combinatorics, Algorithms, and Complexity

__
TR98-012
| 2nd February 1998
__

Meena Mahajan, V Vinay#### Determinant: Old Algorithms, New Insights

__
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

__
TR00-003
| 26th November 1999
__

Matthias Krause, Hans Ulrich Simon#### Determining the Optimal Contrast for Secret Sharing Schemes in Visual Cryptography

__
TR98-077
| 19th December 1998
__

Miklos Ajtai#### Determinism versus Non-Determinism for Linear Time RAMs with Memory Restrictions

Revisions: 1

__
TR11-102
| 31st July 2011
__

Miklos Ajtai#### Determinism Versus Nondeterminism with Arithmetic Tests and Computation

Revisions: 1

__
TR98-072
| 14th December 1998
__

Ziv Bar-Yossef, Oded Goldreich, Avi Wigderson#### Deterministic Amplification of Space Bounded Probabilistic Algorithms.

__
TR13-172
| 1st December 2013
__

Anindya De, Ilias Diakonikolas, Rocco Servedio#### Deterministic Approximate Counting for Degree-$2$ Polynomial Threshold Functions

__
TR13-171
| 1st December 2013
__

Anindya De, Ilias Diakonikolas, Rocco Servedio#### Deterministic Approximate Counting for Juntas of Degree-$2$ Polynomial Threshold Functions

__
TR08-065
| 11th July 2008
__

Noga Alon, Rina Panigrahy, Sergey Yekhanin#### Deterministic Approximation Algorithms for the Nearest Codeword Problem

__
TR10-015
| 8th February 2010
__

Maurice Jansen, Youming Qiao, Jayalal Sarma#### Deterministic Black-Box Identity Testing $\pi$-Ordered Algebraic Branching Programs

__
TR04-050
| 13th June 2004
__

Michelle Effros, Leonard Schulman#### Deterministic clustering with data nets

__
TR15-050
| 4th April 2015
__

Mika Göös, Toniann Pitassi, Thomas Watson#### Deterministic Communication vs. Partition Number

Revisions: 1

__
TR12-166
| 25th November 2012
__

Elad Haramaty, Madhu Sudan#### Deterministic Compression with Uncertain Priors

__
TR10-162
| 30th October 2010
__

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

__
TR05-108
| 28th September 2005
__

Ariel Gabizon, Ran Raz#### Deterministic Extractors for Affine Sources over Large Fields

__
TR08-042
| 6th April 2008
__

Zeev Dvir#### Deterministic Extractors for Algebraic Sources

__
TR05-109
| 28th September 2005
__

Ariel Gabizon, Ran Raz, Ronen Shaltiel#### Deterministic Extractors for Bit-fixing Sources by Obtaining an Independent Seed

__
TR07-089
| 13th September 2007
__

Parikshit Gopalan, Venkatesan Guruswami#### Deterministic Hardness Amplification via Local GMD Decoding

__
TR14-158
| 26th November 2014
__

Rohit Gurjar, Arpita Korwar, Nitin Saxena, Thomas Thierauf#### Deterministic Identity Testing for Sum of Read Once ABPs

Revisions: 2

__
TR10-084
| 14th May 2010
__

Maurice Jansen, Youming Qiao, Jayalal Sarma#### Deterministic Identity Testing of Read-Once Algebraic Branching Programs

__
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

__
TR12-068
| 25th May 2012
__

Manuel Arora, Gábor Ivanyos, Marek Karpinski, Nitin Saxena#### Deterministic Polynomial Factoring and Association Schemes

__
TR09-058
| 4th July 2009
__

Gábor Ivanyos, Marek Karpinski, Nitin Saxena#### Deterministic Polynomial Time Algorithms for Matrix Completion Problems

__
TR14-179
| 20th December 2014
__

Salman Beigi, Omid Etesami, Amin Gohari#### Deterministic Randomness Extraction from Generalized and Distributed Santha-Vazirani Sources

__
TR96-004
| 18th January 1996
__

Shiva Chaudhuri, Jaikumar Radhakrishnan#### Deterministic Restrictions in Circuit Complexity

__
TR00-075
| 7th September 2000
__

Andreas Klein, Martin Kutrib#### Deterministic Turing Machines in the Range between Real-Time and Linear-Time

__
TR13-059
| 9th April 2013
__

Lior Gishboliner, Asaf Shapira#### Deterministic vs Non-deterministic Graph Property Testing

__
TR14-168
| 8th December 2014
__

Ilya Volkovich#### Deterministically Factoring Sparse Polynomials into Multilinear Factors

__
TR07-124
| 23rd November 2007
__

Nitin Saxena#### Diagonal Circuit Identity Testing and Lower Bounds

__
TR04-018
| 24th January 2004
__

Jan Krajicek#### Diagonalization in proof complexity

__
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

__
TR15-084
| 21st May 2015
__

Or Ordentlich, Ofer Shayevitz, Omri Weinstein#### Dictatorship is the Most Informative Balanced Function at the Extremes

Revisions: 2

__
TR05-160
| 10th December 2005
__

Xiaoyang Gu, Jack H. Lutz#### Dimension Characterizations of Complexity Classes

__
TR14-162
| 28th November 2014
__

Michael Forbes, Venkatesan Guruswami#### Dimension Expanders via Rank Condensers

__
TR06-080
| 16th June 2006
__

David Doty#### Dimension Extractors

__
TR04-104
| 19th November 2004
__

Maria Lopez-Valdes, Mayordomo Elvira#### Dimension is compression

__
TR17-125
| 7th August 2017
__

Badih Ghazi, Pritish Kamath, Prasad Raghavendra#### Dimension Reduction for Polynomials over Gaussian Space and Applications

__
TR05-089
| 30th July 2005
__

Xiaoyang Gu, Jack H. Lutz, Philippe Moser#### Dimensions of Copeland-Erdos Sequences

__
TR13-179
| 15th December 2013
__

Irit Dinur, David Steurer#### Direct Product Testing

__
TR14-182
| 22nd December 2014
__

Dana Moshkovitz#### Direct Product Testing With Nearly Identical Sets

Comments: 1

__
TR07-064
| 19th June 2007
__

Rahul Jain, Hartmut Klauck, Ashwin Nayak#### Direct Product Theorems for Communication Complexity via Subdistribution Bounds

__
TR13-035
| 6th March 2013
__

Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff#### Direct product via round-preserving compression

Revisions: 1

__
TR12-143
| 5th November 2012
__

Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff#### Direct Products in Communication Complexity

Revisions: 2

__
TR13-079
| 2nd June 2013
__

Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff#### Direct Sum Fails for Zero Error Average Communication

__
TR14-002
| 8th January 2014
__

Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, Igor Shinkar#### Direct Sum Testing

__
TR09-044
| 6th May 2009
__

Boaz Barak, Mark Braverman, Xi Chen, Anup Rao#### Direct Sums in Randomized Communication Complexity

__
TR17-153
| 9th October 2017
__

Pranjal Dutta, Nitin Saxena, Amit Sinhababu#### Discovering the roots: Uniform closure results for algebraic classes under factoring

__
TR07-050
| 25th May 2007
__

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

__
TR16-108
| 16th July 2016
__

Michael Rudow#### Discrete Logarithm and Minimum Circuit Size

__
TR03-011
| 17th February 2003
__

Christian Glaßer, Alan L. Selman, Samik Sengupta, Liyu Zhang#### Disjoint NP-Pairs

__
TR05-083
| 24th July 2005
__

Olaf Beyersdorff#### Disjoint NP-Pairs from Propositional Proof Systems

__
TR08-003
| 25th December 2007
__

Troy Lee, Adi Shraibman#### Disjointness is hard in the multi-party number-on-the-forehead model

__
TR11-127
| 18th September 2011
__

Ronen Shaltiel#### Dispersers for affine sources with sub-polynomial entropy

__
TR06-102
| 15th August 2006
__

Luis Rademacher, Santosh Vempala#### Dispersion of Mass and the Complexity of Randomized Geometric Algorithms

__
TR05-021
| 14th February 2005
__

Stasys Jukna#### Disproving the single level conjecture

Revisions: 2
,
Comments: 1

__
TR10-119
| 27th July 2010
__

Michal Moshkovitz#### Distance Estimators with Sublogarithmic Number of Queries

__
TR18-079
| 19th April 2018
__

Jayadev Acharya, Clement Canonne, Himanshu Tyagi#### Distributed Simulation and Distributed Inference

__
TR11-089
| 7th June 2011
__

Paul Valiant#### Distribution Free Evolvability of Polynomial Functions over all Convex Loss Functions

Revisions: 1

__
TR12-186
| 27th December 2012
__

Andreas Krebs, Nutan Limaye#### DLOGTIME-Proof Systems

__
TR12-060
| 16th May 2012
__

Parikshit Gopalan, Raghu Meka, Omer Reingold#### DNF Sparsification and a Faster Deterministic Counting

Revisions: 2

__
TR05-075
| 4th July 2005
__

Martin Dyer, Leslie Ann Goldberg, Mark Jerrum#### Dobrushin conditions and Systematic Scan

Revisions: 1

__
TR17-109
| 22nd June 2017
__

Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, Shadab Romani#### Does Looking Inside a Circuit Help?

__
TR06-114
| 22nd August 2006
__

Carl Bosley, Yevgeniy Dodis#### Does Privacy Require True Randomness?

__
TR17-069
| 17th April 2017
__

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

__
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

__
TR03-003
| 19th December 2002
__

Fahiem Bacchus, Shannon Dalmao#### DPLL with Caching: A new algorithm for #SAT and Bayesian Inference

__
TR13-032
| 26th February 2013
__

Mark Bun, Justin Thaler#### Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities

Revisions: 2

__
TR17-062
| 9th April 2017
__

Arkadev Chattopadhyay, Nikhil Mande#### Dual polynomials and communication complexity of XOR functions

__
TR15-041
| 25th March 2015
__

Mark Bun, Justin Thaler#### Dual Polynomials for Collision and Element Distinctness

__
TR14-122
| 30th September 2014
__

Eric Allender, Anna Gal, Ian Mertz#### Dual VP Classes

Revisions: 2

__
TR95-020
| 8th March 1995
__

William Hurwood#### Dynamic Fault Diagnosis

__
TR01-090
| 28th November 2001
__

Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk#### Dynamic Process Graphs and the Complexity of Scheduling

Dmitry Sokolov

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

Badih Ghazi, Pritish Kamath, Madhu Sudan

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

Irit Dinur, Elena Grigorescu, Swastik Kopparty, Madhu Sudan

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

Oded Goldreich

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

Roei Tell

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

Vince Grolmusz

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 >>>Parikshit Gopalan, Rocco Servedio, Avishay Tal, Avi Wigderson

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

Albert Atserias, Anuj Dawar

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

Shafi Goldwasser, Guy Rothblum, Yael Tauman Kalai

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

Irit Dinur, Tali Kaufman

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

Omer Reingold, Luca Trevisan, Madhur Tulsiani, Salil Vadhan

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

Nader Bshouty

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

Olaf Beyersdorff, Joshua Blinkhorn

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

Joshua Brody, Mario Sanchez

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

Sajin Koroth, Jayalal Sarma

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

Amir Shpilka, Avi Wigderson

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

Partha Mukhopadhyay

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

Shiteng Chen, Periklis Papakonstantinou

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

Boaz Barak, Shien Jin Ong, Salil Vadhan

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

Daniel Rolf

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

Evgeny Dantsin, Alexander Wolpert

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

Oded Goldreich, Avi Wigderson

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

Valentine Kabanets

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.

Eyal Kaplan, Moni Naor, Omer Reingold

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

Irit Dinur, Or Meir

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

Eyal Rozenman, Salil Vadhan

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

Dan Gutfreund, Akinori Kawachi

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

Nader Bshouty

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

Stasys Jukna

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

Dieter van Melkebeek, Gautam Prakriya

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

Rahul Arora, Ashu Gupta, Rohit Gurjar, Raghunath Tewari

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

Bin Fu

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

Matthew Anderson, Dieter van Melkebeek, Ilya Volkovich

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

Valentine Kabanets, Russell Impagliazzo

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

Avi Wigderson, David Xiao

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

Vikraman Arvind, Partha Mukhopadhyay

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

Bruno Durand, Alexander Shen, Nikolay Vereshchagin

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

Xin Li

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

Joshua Grochow, Cris Moore

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

Peter Floderus, Andrzej Lingas, Mia Persson, Dzmitry Sledneu

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

Meena Mahajan, V Vinay

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

Meena Mahajan, V Vinay

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

Stephen A. Fenner, Frederic Green, Steven Homer, Randall Pruim

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

Matthias Krause, Hans Ulrich Simon

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

Miklos Ajtai

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

Miklos Ajtai

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

Ziv Bar-Yossef, Oded Goldreich, Avi Wigderson

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

Anindya De, Ilias Diakonikolas, Rocco Servedio

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

Anindya De, Ilias Diakonikolas, Rocco Servedio

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

Noga Alon, Rina Panigrahy, Sergey Yekhanin

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

Maurice Jansen, Youming Qiao, Jayalal Sarma

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

Michelle Effros, Leonard Schulman

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

Mika Göös, Toniann Pitassi, Thomas Watson

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

Elad Haramaty, Madhu Sudan

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

Zohar Karnin

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

Ariel Gabizon, Ran Raz

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

Zeev Dvir

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

Ariel Gabizon, Ran Raz, Ronen Shaltiel

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

Parikshit Gopalan, Venkatesan Guruswami

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

Rohit Gurjar, Arpita Korwar, Nitin Saxena, Thomas Thierauf

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

Maurice Jansen, Youming Qiao, Jayalal Sarma

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

Zohar Karnin, Partha Mukhopadhyay, Amir Shpilka, Ilya Volkovich

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

Manuel Arora, Gábor Ivanyos, Marek Karpinski, Nitin Saxena

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

Gábor Ivanyos, Marek Karpinski, Nitin Saxena

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

Salman Beigi, Omid Etesami, Amin Gohari

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

Shiva Chaudhuri, Jaikumar Radhakrishnan

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

Andreas Klein, Martin Kutrib

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

Lior Gishboliner, Asaf Shapira

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

Ilya Volkovich

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

Nitin Saxena

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

Jan Krajicek

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

Ondrej Klíma, Pascal Tesson, Denis Thérien

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

Or Ordentlich, Ofer Shayevitz, Omri Weinstein

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

Xiaoyang Gu, Jack H. Lutz

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

Michael Forbes, Venkatesan Guruswami

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

David Doty

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

Maria Lopez-Valdes, Mayordomo Elvira

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

Badih Ghazi, Pritish Kamath, Prasad Raghavendra

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

Xiaoyang Gu, Jack H. Lutz, Philippe Moser

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

Irit Dinur, David Steurer

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

Dana Moshkovitz

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

Rahul Jain, Hartmut Klauck, Ashwin Nayak

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

Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff

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

Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff

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

Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff

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

Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, Igor Shinkar

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

Boaz Barak, Mark Braverman, Xi Chen, Anup Rao

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

Pranjal Dutta, Nitin Saxena, Amit Sinhababu

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

Arkadev Chattopadhyay

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

Michael Rudow

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

Christian Glaßer, Alan L. Selman, Samik Sengupta, Liyu Zhang

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

Olaf Beyersdorff

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

Troy Lee, Adi Shraibman

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

Ronen Shaltiel

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

Luis Rademacher, Santosh Vempala

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

Stasys Jukna

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

Michal Moshkovitz

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

Jayadev Acharya, Clement Canonne, Himanshu Tyagi

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

Paul Valiant

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

Andreas Krebs, Nutan Limaye

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

Parikshit Gopalan, Raghu Meka, Omer Reingold

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

Martin Dyer, Leslie Ann Goldberg, Mark Jerrum

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

Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, Shadab Romani

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

Carl Bosley, Yevgeniy Dodis

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

Jacob Steinhardt

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

Zi-Wen Liu, Christopher Perry, Yechao Zhu, Dax Enshan Koh, Scott Aaronson

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

Fahiem Bacchus, Shannon Dalmao

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

Mark Bun, Justin Thaler

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

Arkadev Chattopadhyay, Nikhil Mande

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

Mark Bun, Justin Thaler

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

Eric Allender, Anna Gal, Ian Mertz

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

William Hurwood

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

Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk

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