Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Thomas Watson:

TR20-097 | 30th June 2020
Md Lutfar Rahman, Thomas Watson

6-Uniform Maker-Breaker Game Is PSPACE-Complete

In a STOC 1976 paper, Schaefer proved that it is PSPACE-complete to determine the winner of the so-called Maker-Breaker game on a given set system, even when every set has size at most 11. Since then, there has been no improvement on this result. We prove that the game remains ... more >>>

TR19-160 | 10th November 2019
Md Lutfar Rahman, Thomas Watson

Tractable Unordered 3-CNF Games

The classic TQBF problem can be viewed as a game in which two players alternate turns assigning truth values to a CNF formula's variables in a prescribed order, and the winner is determined by whether the CNF gets satisfied. The complexity of deciding which player has a winning strategy in ... more >>>

TR19-066 | 3rd May 2019
Thomas Watson

A Lower Bound for Sampling Disjoint Sets

Revisions: 2

Suppose Alice and Bob each start with private randomness and no other input, and they wish to engage in a protocol in which Alice ends up with a set $x\subseteq[n]$ and Bob ends up with a set $y\subseteq[n]$, such that $(x,y)$ is uniformly distributed over all pairs of disjoint sets. ... more >>>

TR19-043 | 12th March 2019
Toniann Pitassi, Morgan Shirley, Thomas Watson

Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity

Revisions: 1

We study the Boolean Hierarchy in the context of two-party communication complexity, as well as the analogous hierarchy defined with one-sided error randomness instead of nondeterminism. Our results provide a complete picture of the relationships among complexity classes within and across these two hierarchies. In particular, we prove a query-to-communication ... more >>>

TR18-058 | 5th April 2018
Thomas Watson

Amplification with One NP Oracle Query

Revisions: 1

We provide a complete picture of the extent to which amplification of success probability is possible for randomized algorithms having access to one NP oracle query, in the settings of two-sided, one-sided, and zero-sided error. We generalize this picture to amplifying one-query algorithms with q-query algorithms, and we show our ... more >>>

TR18-039 | 23rd February 2018
Md Lutfar Rahman, Thomas Watson

Complexity of Unordered CNF Games

Revisions: 1

The classic TQBF problem is to determine who has a winning strategy in a game played on a given CNF formula, where the two players alternate turns picking truth values for the variables in a given order, and the winner is determined by whether the CNF gets satisfied. We study ... more >>>

TR17-139 | 18th September 2017
Thomas Watson

A ZPP^NP[1] Lifting Theorem

Revisions: 1

The complexity class ZPP^NP[1] (corresponding to zero-error randomized algorithms with access to one NP oracle query) is known to have a number of curious properties. We further explore this class in the settings of time complexity, query complexity, and communication complexity.

For starters, we provide a new characterization: ZPP^NP[1] equals ... more >>>

TR17-053 | 22nd March 2017
Mika Göös, Toniann Pitassi, Thomas Watson

Query-to-Communication Lifting for BPP

Revisions: 1

For any $n$-bit boolean function $f$, we show that the randomized communication complexity of the composed function $f\circ g^n$, where $g$ is an index gadget, is characterized by the randomized decision tree complexity of $f$. In particular, this means that many query complexity separations involving randomized models (e.g., classical vs.\ ... more >>>

TR17-031 | 15th February 2017
Thomas Watson

Quadratic Simulations of Merlin-Arthur Games

Revisions: 1

The known proofs of $\text{MA}\subseteq\text{PP}$ incur a quadratic overhead in the running time. We prove that this quadratic overhead is necessary for black-box simulations; in particular, we obtain an oracle relative to which $\text{MA-TIME}(t)\not\subseteq\text{P-TIME}(o(t^2))$. We also show that 2-sided-error Merlin--Arthur games can be simulated by 1-sided-error Arthur--Merlin games with quadratic ... more >>>

TR17-024 | 16th February 2017
Mika Göös, Pritish Kamath, Toniann Pitassi, Thomas Watson

Query-to-Communication Lifting for P^NP

Revisions: 1

We prove that the $\text{P}^{\small\text{NP}}$-type query complexity (alternatively, decision list width) of any boolean function $f$ is quadratically related to the $\text{P}^{\small\text{NP}}$-type communication complexity of a lifted version of $f$. As an application, we show that a certain "product" lower bound method of Impagliazzo and Williams (CCC 2010) fails to ... more >>>

TR16-170 | 3rd November 2016
Thomas Watson

Communication Complexity of Statistical Distance

Revisions: 1

We prove nearly matching upper and lower bounds on the randomized communication complexity of the following problem: Alice and Bob are each given a probability distribution over $n$ elements, and they wish to estimate within $\pm\epsilon$ the statistical (total variation) distance between their distributions. For some range of parameters, there ... more >>>

TR16-148 | 23rd September 2016
Thomas Watson

Communication Complexity with Small Advantage

Revisions: 1

We study problems in randomized communication complexity when the protocol is only required to attain some small advantage over purely random guessing, i.e., it produces the correct output with probability at least $\epsilon$ greater than one over the codomain size of the function. Previously, Braverman and Moitra (STOC 2013) showed ... more >>>

TR16-070 | 24th April 2016
Mika Göös, Rahul Jain, Thomas Watson

Extension Complexity of Independent Set Polytopes

Revisions: 1

We exhibit an $n$-node graph whose independent set polytope requires extended formulations of size exponential in $\Omega(n/\log n)$. Previously, no explicit examples of $n$-dimensional $0/1$-polytopes were known with extension complexity larger than exponential in $\Theta(\sqrt{n})$. Our construction is inspired by a relatively little-known connection between extended formulations and (monotone) circuit ... more >>>

TR15-169 | 23rd October 2015
Mika Göös, T.S. Jayram, Toniann Pitassi, Thomas Watson

Randomized Communication vs. Partition Number

Revisions: 1

We show that \emph{randomized} communication complexity can be superlogarithmic in the partition number of the associated communication matrix, and we obtain near-optimal \emph{randomized} lower bounds for the Clique vs.\ Independent Set problem. These results strengthen the deterministic lower bounds obtained in prior work (G\"o\"os, Pitassi, and Watson, {\small FOCS~2015}).

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

TR15-049 | 3rd April 2015
Mika Göös, Toniann Pitassi, Thomas Watson

The Landscape of Communication Complexity Classes

Revisions: 1

We prove several results which, together with prior work, provide a nearly-complete picture of the relationships among classical communication complexity classes between $P$ and $PSPACE$, short of proving lower bounds against classes for which no explicit lower bounds were already known. Our article also serves as an up-to-date survey on ... more >>>

TR14-147 | 6th November 2014
Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, David Zuckerman

Rectangles Are Nonnegative Juntas

Revisions: 1

We develop a new method to prove communication lower bounds for composed functions of the form $f\circ g^n$ where $f$ is any boolean function on $n$ inputs and $g$ is a sufficiently ``hard'' two-party gadget. Our main structure theorem states that each rectangle in the communication matrix of $f \circ ... more >>>

TR14-078 | 7th June 2014
Mika Göös, Toniann Pitassi, Thomas Watson

Zero-Information Protocols and Unambiguity in Arthur-Merlin Communication

We study whether information complexity can be used to attack the long-standing open problem of proving lower bounds against Arthur--Merlin (AM) communication protocols. Our starting point is to show that---in contrast to plain randomized communication complexity---every boolean function admits an AM communication protocol where on each yes-input, the distribution of ... more >>>

TR14-055 | 17th April 2014
Mika Göös, Thomas Watson

Communication Complexity of Set-Disjointness for All Probabilities

Revisions: 1

We study set-disjointness in a generalized model of randomized two-party communication where the probability of acceptance must be at least alpha(n) on yes-inputs and at most beta(n) on no-inputs, for some functions alpha(n)>beta(n). Our main result is a complete characterization of the private-coin communication complexity of set-disjointness for all functions ... more >>>

TR13-124 | 9th September 2013
Thomas Watson

The Complexity of Deciding Statistical Properties of Samplable Distributions

Revisions: 2

We consider the problems of deciding whether the joint distribution sampled by a given circuit satisfies certain statistical properties such as being i.i.d., being exchangeable, being pairwise independent, having two coordinates with identical marginals, having two uncorrelated coordinates, and many other variants. We give a proof that simultaneously shows all ... more >>>

TR12-070 | 26th May 2012
Thomas Watson

The Complexity of Estimating Min-Entropy

Revisions: 1

Goldreich, Sahai, and Vadhan (CRYPTO 1999) proved that the promise problem for estimating the Shannon entropy of a distribution sampled by a given circuit is NISZK-complete. We consider the analogous problem for estimating the min-entropy and prove that it is SBP-complete, even when restricted to 3-local samplers. For logarithmic-space samplers, ... more >>>

TR12-026 | 27th March 2012
Thomas Watson

Time Hierarchies for Sampling Distributions

Revisions: 2

We prove that for every constant $k\ge 2$, every polynomial time bound $t$, and every polynomially small $\epsilon$, there exists a family of distributions on $k$ elements that can be sampled exactly in polynomial time but cannot be sampled within statistical distance $1-1/k-\epsilon$ in time $t$. Our proof involves reducing ... more >>>

TR11-120 | 6th September 2011
Thomas Watson

Advice Lower Bounds for the Dense Model Theorem

Revisions: 1

We prove a lower bound on the amount of nonuniform advice needed by black-box reductions for the Dense Model Theorem of Green, Tao, and Ziegler, and of Reingold, Trevisan, Tulsiani, and Vadhan. The latter theorem roughly says that for every distribution $D$ that is $\delta$-dense in a distribution that is ... more >>>

TR11-097 | 7th July 2011
Thomas Watson

Lift-and-Project Integrality Gaps for the Traveling Salesperson Problem

Revisions: 1

We study the lift-and-project procedures of Lovasz-Schrijver and Sherali-Adams applied to the standard linear programming relaxation of the traveling salesperson problem with triangle inequality. For the asymmetric TSP tour problem, Charikar, Goemans, and Karloff (FOCS 2004) proved that the integrality gap of the standard relaxation is at least 2. We ... more >>>

TR11-037 | 18th March 2011
Anindya De, Thomas Watson

Extractors and Lower Bounds for Locally Samplable Sources

Revisions: 3

We consider the problem of extracting randomness from sources that are efficiently samplable, in the sense that each output bit of the sampler only depends on some small number $d$ of the random input bits. As our main result, we construct a deterministic extractor that, given any $d$-local source with ... more >>>

TR10-168 | 9th November 2010
Thomas Watson

Pseudorandom Generators for Combinatorial Checkerboards

Revisions: 2

We define a combinatorial checkerboard to be a function $f:\{1,\ldots,m\}^d\to\{1,-1\}$ of the form $f(u_1,\ldots,u_d)=\prod_{i=1}^df_i(u_i)$ for some functions $f_i:\{1,\ldots,m\}\to\{1,-1\}$. This is a variant of combinatorial rectangles, which can be defined in the same way but using $\{0,1\}$ instead of $\{1,-1\}$. We consider the problem of constructing explicit pseudorandom generators for combinatorial ... more >>>

TR10-147 | 22nd September 2010
Dieter van Melkebeek, Thomas Watson

Time-Space Efficient Simulations of Quantum Computations

Revisions: 1

We give two time- and space-efficient simulations of quantum computations with
intermediate measurements, one by classical randomized computations with
unbounded error and the other by quantum computations that use an arbitrary
fixed universal set of gates. Specifically, our simulations show that every
language solvable by a bounded-error quantum algorithm running ... more >>>

TR10-126 | 12th August 2010
Thomas Watson

Query Complexity in Errorless Hardness Amplification

Revisions: 2

An errorless circuit for a boolean function is one that outputs the correct answer or ``don't know'' on each input (and never outputs the wrong answer). The goal of errorless hardness amplification is to show that if $f$ has no size $s$ errorless circuit that outputs ``don't know'' on at ... more >>>

TR10-042 | 12th March 2010
Thomas Watson

Relativized Worlds Without Worst-Case to Average-Case Reductions for NP

Revisions: 3

We prove that relative to an oracle, there is no worst-case to errorless-average-case reduction for $\NP$. This result is the first progress on an open problem posed by Impagliazzo in 1995, namely to construct an oracle relative to which $\NP$ is worst-case hard but errorless-average-case easy. We also handle classes ... more >>>

TR08-017 | 16th December 2007
Thomas Watson, Dieter van Melkebeek

A Quantum Time-Space Lower Bound for the Counting Hierarchy

We obtain the first nontrivial time-space lower bound for quantum algorithms solving problems related to satisfiability. Our bound applies to MajSAT and MajMajSAT, which are complete problems for the first and second levels of the counting hierarchy, respectively. We prove that for every real $d$ and every positive real $\epsilon$ ... more >>>

ISSN 1433-8092 | Imprint