All reports by Author Thomas Watson:

__
TR20-097
| 30th June 2020
__

Md Lutfar Rahman, Thomas Watson#### 6-Uniform Maker-Breaker Game Is PSPACE-Complete

__
TR19-160
| 10th November 2019
__

Md Lutfar Rahman, Thomas Watson#### Tractable Unordered 3-CNF Games

__
TR19-066
| 3rd May 2019
__

Thomas Watson#### A Lower Bound for Sampling Disjoint Sets

Revisions: 2

__
TR19-043
| 12th March 2019
__

Toniann Pitassi, Morgan Shirley, Thomas Watson#### Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity

Revisions: 1

__
TR18-058
| 5th April 2018
__

Thomas Watson#### Amplification with One NP Oracle Query

Revisions: 1

__
TR18-039
| 23rd February 2018
__

Md Lutfar Rahman, Thomas Watson#### Complexity of Unordered CNF Games

Revisions: 1

__
TR17-139
| 18th September 2017
__

Thomas Watson#### A ZPP^NP[1] Lifting Theorem

Revisions: 1

__
TR17-053
| 22nd March 2017
__

Mika Göös, Toniann Pitassi, Thomas Watson#### Query-to-Communication Lifting for BPP

Revisions: 1

__
TR17-031
| 15th February 2017
__

Thomas Watson#### Quadratic Simulations of Merlin-Arthur Games

Revisions: 1

__
TR17-024
| 16th February 2017
__

Mika Göös, Pritish Kamath, Toniann Pitassi, Thomas Watson#### Query-to-Communication Lifting for P^NP

Revisions: 1

__
TR16-170
| 3rd November 2016
__

Thomas Watson#### Communication Complexity of Statistical Distance

Revisions: 1

__
TR16-148
| 23rd September 2016
__

Thomas Watson#### Communication Complexity with Small Advantage

Revisions: 1

__
TR16-070
| 24th April 2016
__

Mika Göös, Rahul Jain, Thomas Watson#### Extension Complexity of Independent Set Polytopes

Revisions: 1

__
TR15-169
| 23rd October 2015
__

Mika Göös, T.S. Jayram, Toniann Pitassi, Thomas Watson#### Randomized Communication vs. Partition Number

Revisions: 1

__
TR15-050
| 4th April 2015
__

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

Revisions: 1

__
TR15-049
| 3rd April 2015
__

Mika Göös, Toniann Pitassi, Thomas Watson#### The Landscape of Communication Complexity Classes

Revisions: 1

__
TR14-147
| 6th November 2014
__

Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, David Zuckerman#### Rectangles Are Nonnegative Juntas

Revisions: 1

__
TR14-078
| 7th June 2014
__

Mika Göös, Toniann Pitassi, Thomas Watson#### Zero-Information Protocols and Unambiguity in Arthur-Merlin Communication

__
TR14-055
| 17th April 2014
__

Mika Göös, Thomas Watson#### Communication Complexity of Set-Disjointness for All Probabilities

Revisions: 1

__
TR13-124
| 9th September 2013
__

Thomas Watson#### The Complexity of Deciding Statistical Properties of Samplable Distributions

Revisions: 2

__
TR12-070
| 26th May 2012
__

Thomas Watson#### The Complexity of Estimating Min-Entropy

Revisions: 1

__
TR12-026
| 27th March 2012
__

Thomas Watson#### Time Hierarchies for Sampling Distributions

Revisions: 2

__
TR11-120
| 6th September 2011
__

Thomas Watson#### Advice Lower Bounds for the Dense Model Theorem

Revisions: 1

__
TR11-097
| 7th July 2011
__

Thomas Watson#### Lift-and-Project Integrality Gaps for the Traveling Salesperson Problem

Revisions: 1

__
TR11-037
| 18th March 2011
__

Anindya De, Thomas Watson#### Extractors and Lower Bounds for Locally Samplable Sources

Revisions: 3

__
TR10-168
| 9th November 2010
__

Thomas Watson#### Pseudorandom Generators for Combinatorial Checkerboards

Revisions: 2

__
TR10-147
| 22nd September 2010
__

Dieter van Melkebeek, Thomas Watson#### Time-Space Efficient Simulations of Quantum Computations

Revisions: 1

__
TR10-126
| 12th August 2010
__

Thomas Watson#### Query Complexity in Errorless Hardness Amplification

Revisions: 2

__
TR10-042
| 12th March 2010
__

Thomas Watson#### Relativized Worlds Without Worst-Case to Average-Case Reductions for NP

Revisions: 3

__
TR08-017
| 16th December 2007
__

Thomas Watson, Dieter van Melkebeek#### A Quantum Time-Space Lower Bound for the Counting Hierarchy

Md Lutfar Rahman, Thomas Watson

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

Md Lutfar Rahman, Thomas Watson

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

Thomas Watson

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

Toniann Pitassi, Morgan Shirley, Thomas Watson

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

Thomas Watson

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

Md Lutfar Rahman, Thomas Watson

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

Thomas Watson

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

Mika Göös, Toniann Pitassi, Thomas Watson

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

Thomas Watson

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

Mika Göös, Pritish Kamath, Toniann Pitassi, Thomas Watson

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

Thomas Watson

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

Thomas Watson

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

Mika Göös, Rahul Jain, Thomas Watson

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

Mika Göös, T.S. Jayram, Toniann Pitassi, Thomas Watson

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

Mika Göös, Toniann Pitassi, Thomas Watson

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

Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, David Zuckerman

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

Mika Göös, Toniann Pitassi, Thomas Watson

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

Mika Göös, Thomas Watson

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

Thomas Watson

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

Thomas Watson

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

Thomas Watson

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

Thomas Watson

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

Thomas Watson

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

Anindya De, Thomas Watson

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

Thomas Watson

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

Dieter van Melkebeek, Thomas Watson

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

Thomas Watson

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

Thomas Watson

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

Thomas Watson, Dieter van Melkebeek

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