Search Results

Documents authored by Watson, Thomas

Document
DOI: 10.4230/LIPIcs.FSTTCS.2022.26
Complexity of Fault Tolerant Query Complexity

Authors: Ramita Maharjan and Thomas Watson

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Abstract
In the model of fault tolerant decision trees introduced by Kenyon and Yao, there is a known upper bound E on the total number of queries that may be faulty (i.e., get the wrong bit). We consider this computational problem: Given as input the truth table of a function f: {0,1}ⁿ → {0,1} and a value of E, find the minimum possible height (worst-case number of queries) of any decision tree that computes f while tolerating up to E many faults. We design an algorithm for this problem that runs in time Õ(binom(n+E,E)⋅(2E+3)ⁿ), which is polynomial in the size of the truth table when E is a constant. This generalizes a standard algorithm for the non-fault tolerant setting.
Cite as

Ramita Maharjan and Thomas Watson. Complexity of Fault Tolerant Query Complexity. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 26:1-26:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{maharjan_et_al:LIPIcs.FSTTCS.2022.26,
  author =	{Maharjan, Ramita and Watson, Thomas},
  title =	{{Complexity of Fault Tolerant Query Complexity}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{26:1--26:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.26},
  URN =		{urn:nbn:de:0030-drops-174185},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.26},
  annote =	{Keywords: Fault, Tolerant, Query, Complexity}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2022.31
Erdős-Selfridge Theorem for Nonmonotone CNFs

Authors: Md Lutfar Rahman and Thomas Watson

Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)

Abstract
In an influential paper, Erdős and Selfridge introduced the Maker-Breaker game played on a hypergraph, or equivalently, on a monotone CNF. The players take turns assigning values to variables of their choosing, and Breaker’s goal is to satisfy the CNF, while Maker’s goal is to falsify it. The Erdős-Selfridge Theorem says that the least number of clauses in any monotone CNF with k literals per clause where Maker has a winning strategy is Θ(2^k). We study the analogous question when the CNF is not necessarily monotone. We prove bounds of Θ(√2 ^k) when Maker plays last, and Ω(1.5^k) and O(r^k) when Breaker plays last, where r = (1+√5)/2≈ 1.618 is the golden ratio.
Cite as

Md Lutfar Rahman and Thomas Watson. Erdős-Selfridge Theorem for Nonmonotone CNFs. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 31:1-31:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{rahman_et_al:LIPIcs.SWAT.2022.31,
  author =	{Rahman, Md Lutfar and Watson, Thomas},
  title =	{{Erd\H{o}s-Selfridge Theorem for Nonmonotone CNFs}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{31:1--31:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-236-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{227},
  editor =	{Czumaj, Artur and Xin, Qin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.31},
  URN =		{urn:nbn:de:0030-drops-161916},
  doi =		{10.4230/LIPIcs.SWAT.2022.31},
  annote =	{Keywords: Game, nonmonotone, CNFs}
}
Document
DOI: 10.4230/LIPIcs.STACS.2021.57
6-Uniform Maker-Breaker Game Is PSPACE-Complete

Authors: Md Lutfar Rahman and Thomas Watson

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

Abstract
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 PSPACE-complete even when every set has size 6.
Cite as

Md Lutfar Rahman and Thomas Watson. 6-Uniform Maker-Breaker Game Is PSPACE-Complete. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 57:1-57:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{rahman_et_al:LIPIcs.STACS.2021.57,
  author =	{Rahman, Md Lutfar and Watson, Thomas},
  title =	{{6-Uniform Maker-Breaker Game Is PSPACE-Complete}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{57:1--57:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.57},
  URN =		{urn:nbn:de:0030-drops-137020},
  doi =		{10.4230/LIPIcs.STACS.2021.57},
  annote =	{Keywords: Game, Maker-Breaker, Complexity, Reduction, PSPACE-complete, NL-hard}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.28
When Is Amplification Necessary for Composition in Randomized Query Complexity?

Authors: Shalev Ben-David, Mika Göös, Robin Kothari, and Thomas Watson

Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)

Abstract
Suppose we have randomized decision trees for an outer function f and an inner function g. The natural approach for obtaining a randomized decision tree for the composed function (f∘ gⁿ)(x¹,…,xⁿ) = f(g(x¹),…,g(xⁿ)) involves amplifying the success probability of the decision tree for g, so that a union bound can be used to bound the error probability over all the coordinates. The amplification introduces a logarithmic factor cost overhead. We study the question: When is this log factor necessary? We show that when the outer function is parity or majority, the log factor can be necessary, even for models that are more powerful than plain randomized decision trees. Our results are related to, but qualitatively strengthen in various ways, known results about decision trees with noisy inputs.
Cite as

Shalev Ben-David, Mika Göös, Robin Kothari, and Thomas Watson. When Is Amplification Necessary for Composition in Randomized Query Complexity?. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 28:1-28:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bendavid_et_al:LIPIcs.APPROX/RANDOM.2020.28,
  author =	{Ben-David, Shalev and G\"{o}\"{o}s, Mika and Kothari, Robin and Watson, Thomas},
  title =	{{When Is Amplification Necessary for Composition in Randomized Query Complexity?}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{28:1--28:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.28},
  URN =		{urn:nbn:de:0030-drops-126316},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.28},
  annote =	{Keywords: Amplification, composition, query complexity}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.92
Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity

Authors: Toniann Pitassi, Morgan Shirley, and Thomas Watson

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
We investigate the power of randomness in two-party communication complexity. In particular, we study the model where the parties can make a constant number of queries to a function with an efficient one-sided-error randomized protocol. The complexity classes defined by this model comprise the Randomized Boolean Hierarchy, which is analogous to the Boolean Hierarchy but defined with one-sided-error randomness instead of nondeterminism. Our techniques connect the Nondeterministic and Randomized Boolean Hierarchies, and we provide a complete picture of the relationships among complexity classes within and across these two hierarchies. In particular, we prove that the Randomized Boolean Hierarchy does not collapse, and we prove a query-to-communication lifting theorem for all levels of the Nondeterministic Boolean Hierarchy and use it to resolve an open problem stated in the paper by Halstenberg and Reischuk (CCC 1988) which initiated the study of this hierarchy.
Cite as

Toniann Pitassi, Morgan Shirley, and Thomas Watson. Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 92:1-92:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{pitassi_et_al:LIPIcs.ICALP.2020.92,
  author =	{Pitassi, Toniann and Shirley, Morgan and Watson, Thomas},
  title =	{{Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{92:1--92:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.92},
  URN =		{urn:nbn:de:0030-drops-124992},
  doi =		{10.4230/LIPIcs.ICALP.2020.92},
  annote =	{Keywords: Boolean hierarchies, lifting theorems, query complexity}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.51
A Lower Bound for Sampling Disjoint Sets

Authors: Mika Göös and Thomas Watson

Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Abstract
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. We prove that for some constant beta<1, this requires Omega(n) communication even to get within statistical distance 1-beta^n of the target distribution. Previously, Ambainis, Schulman, Ta-Shma, Vazirani, and Wigderson (FOCS 1998) proved that Omega(sqrt{n}) communication is required to get within some constant statistical distance epsilon>0 of the uniform distribution over all pairs of disjoint sets of size sqrt{n}.
Cite as

Mika Göös and Thomas Watson. A Lower Bound for Sampling Disjoint Sets. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 51:1-51:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{goos_et_al:LIPIcs.APPROX-RANDOM.2019.51,
  author =	{G\"{o}\"{o}s, Mika and Watson, Thomas},
  title =	{{A Lower Bound for Sampling Disjoint Sets}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{51:1--51:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.51},
  URN =		{urn:nbn:de:0030-drops-112666},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.51},
  annote =	{Keywords: Communication complexity, set disjointness, sampling}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.96
Amplification with One NP Oracle Query

Authors: Thomas Watson

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
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 inclusions are tight for relativizing techniques.
Cite as

Thomas Watson. Amplification with One NP Oracle Query. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 96:1-96:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{watson:LIPIcs.ICALP.2019.96,
  author =	{Watson, Thomas},
  title =	{{Amplification with One NP Oracle Query}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{96:1--96:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.96},
  URN =		{urn:nbn:de:0030-drops-106726},
  doi =		{10.4230/LIPIcs.ICALP.2019.96},
  annote =	{Keywords: Amplification, NP, oracle, query}
}
Document
DOI: 10.4230/LIPIcs.STACS.2019.59
A ZPP^NP[1] Lifting Theorem

Authors: Thomas Watson

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Abstract
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 the restriction of BPP^{NP[1]} where the algorithm is only allowed to err when it forgoes the opportunity to make an NP oracle query. - Using the above characterization, we prove a query-to-communication lifting theorem, which translates any ZPP^{NP[1]} decision tree lower bound for a function f into a ZPP^{NP[1]} communication lower bound for a two-party version of f. - As an application, we use the above lifting theorem to prove that the ZPP^{NP[1]} communication lower bound technique introduced by Göös, Pitassi, and Watson (ICALP 2016) is not tight. We also provide a "primal" characterization of this lower bound technique as a complexity class.
Cite as

Thomas Watson. A ZPP^NP[1] Lifting Theorem. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 59:1-59:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{watson:LIPIcs.STACS.2019.59,
  author =	{Watson, Thomas},
  title =	{{A ZPP^NP\lbrack1\rbrack Lifting Theorem}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{59:1--59:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.59},
  URN =		{urn:nbn:de:0030-drops-102989},
  doi =		{10.4230/LIPIcs.STACS.2019.59},
  annote =	{Keywords: Query complexity, communication complexity, lifting}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.9
Complexity of Unordered CNF Games

Authors: Md Lutfar Rahman and Thomas Watson

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
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 variants of this game in which the variables may be played in any order, and each turn consists of picking a remaining variable and a truth value for it. - For the version where the set of variables is partitioned into two halves and each player may only pick variables from his/her half, we prove that the problem is PSPACE-complete for 5-CNFs and in P for 2-CNFs. Previously, it was known to be PSPACE-complete for unbounded-width CNFs (Schaefer, STOC 1976). - For the general unordered version (where each variable can be picked by either player), we also prove that the problem is PSPACE-complete for 5-CNFs and in P for 2-CNFs. Previously, it was known to be PSPACE-complete for 6-CNFs (Ahlroth and Orponen, MFCS 2012) and PSPACE-complete for positive 11-CNFs (Schaefer, STOC 1976).
Cite as

Md Lutfar Rahman and Thomas Watson. Complexity of Unordered CNF Games. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 9:1-9:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{rahman_et_al:LIPIcs.ISAAC.2018.9,
  author =	{Rahman, Md Lutfar and Watson, Thomas},
  title =	{{Complexity of Unordered CNF Games}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{9:1--9:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.9},
  URN =		{urn:nbn:de:0030-drops-99574},
  doi =		{10.4230/LIPIcs.ISAAC.2018.9},
  annote =	{Keywords: CNF, Games, PSPACE-complete, SAT, Linear Time}
}
Document
DOI: 10.4230/LIPIcs.CCC.2018.9
Communication Complexity with Small Advantage

Authors: Thomas Watson

Published in: LIPIcs, Volume 102, 33rd Computational Complexity Conference (CCC 2018)

Abstract
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 that the set-intersection function requires Theta(epsilon n) communication to achieve advantage epsilon. Building on this, we prove the same bound for several variants of set-intersection: (1) the classic "tribes" function obtained by composing with And (provided 1/epsilon is at most the width of the And), and (2) the variant where the sets are uniquely intersecting and the goal is to determine partial information about (say, certain bits of the index of) the intersecting coordinate.
Cite as

Thomas Watson. Communication Complexity with Small Advantage. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{watson:LIPIcs.CCC.2018.9,
  author =	{Watson, Thomas},
  title =	{{Communication Complexity with Small Advantage}},
  booktitle =	{33rd Computational Complexity Conference (CCC 2018)},
  pages =	{9:1--9:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-069-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{102},
  editor =	{Servedio, Rocco A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2018.9},
  URN =		{urn:nbn:de:0030-drops-88805},
  doi =		{10.4230/LIPIcs.CCC.2018.9},
  annote =	{Keywords: Communication, complexity, small, advantage}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.49
Communication Complexity of Statistical Distance

Authors: Thomas Watson

Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)

Abstract
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 +-epsilon the statistical (total variation) distance between their distributions. For some range of parameters, there is up to a log(n) factor gap between the upper and lower bounds, and we identify a barrier to using information complexity techniques to improve the lower bound in this case. We also prove a side result that we discovered along the way: the randomized communication complexity of n-bit Majority composed with n-bit Greater-Than is Theta(n log n).
Cite as

Thomas Watson. Communication Complexity of Statistical Distance. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 49:1-49:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{watson:LIPIcs.APPROX-RANDOM.2017.49,
  author =	{Watson, Thomas},
  title =	{{Communication Complexity of Statistical Distance}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{49:1--49:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.49},
  URN =		{urn:nbn:de:0030-drops-75984},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.49},
  annote =	{Keywords: Communication, complexity, statistical, distance}
}
Document
DOI: 10.4230/LIPIcs.CCC.2017.12
Query-to-Communication Lifting for P^NP

Authors: Mika Göös, Pritish Kamath, Toniann Pitassi, and Thomas Watson

Published in: LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017)

Abstract
We prove that the P^NP-type query complexity (alternatively, decision list width) of any boolean function f is quadratically related to the P^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 capture P^NP communication complexity up to polynomial factors, which answers a question of Papakonstantinou, Scheder, and Song (CCC 2014).
Cite as

Mika Göös, Pritish Kamath, Toniann Pitassi, and Thomas Watson. Query-to-Communication Lifting for P^NP. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{goos_et_al:LIPIcs.CCC.2017.12,
  author =	{G\"{o}\"{o}s, Mika and Kamath, Pritish and Pitassi, Toniann and Watson, Thomas},
  title =	{{Query-to-Communication Lifting for P^NP}},
  booktitle =	{32nd Computational Complexity Conference (CCC 2017)},
  pages =	{12:1--12:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-040-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{79},
  editor =	{O'Donnell, Ryan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.12},
  URN =		{urn:nbn:de:0030-drops-75388},
  doi =		{10.4230/LIPIcs.CCC.2017.12},
  annote =	{Keywords: Communication Complexity, Query Complexity, Lifting Theorem, P^NP}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.52
Randomized Communication vs. Partition Number

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

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
We show that randomized communication complexity can be superlogarithmic in the partition number of the associated communication matrix, and we obtain near-optimal randomized lower bounds for the Clique vs. Independent Set problem. These results strengthen the deterministic lower bounds obtained in prior work (Goos, Pitassi, and Watson, FOCS 2015). One of our main technical contributions states that information complexity when the cost is measured with respect to only 1-inputs (or only 0-inputs) is essentially equivalent to information complexity with respect to all inputs.
Cite as

Mika Göös, T. S. Jayram, Toniann Pitassi, and Thomas Watson. Randomized Communication vs. Partition Number. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 52:1-52:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{goos_et_al:LIPIcs.ICALP.2017.52,
  author =	{G\"{o}\"{o}s, Mika and Jayram, T. S. and Pitassi, Toniann and Watson, Thomas},
  title =	{{Randomized Communication vs. Partition Number}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{52:1--52:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.52},
  URN =		{urn:nbn:de:0030-drops-74861},
  doi =		{10.4230/LIPIcs.ICALP.2017.52},
  annote =	{Keywords: communication complexity, partition number, information complexity}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2016.86
The Landscape of Communication Complexity Classes

Authors: Mika Göös, Toniann Pitassi, and Thomas Watson

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Abstract
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 the state of structural communication complexity. Among our new results we show that MA !subseteq ZPP^{NP[1]}, that is, Merlin–Arthur proof systems cannot be simulated by zero-sided error randomized protocols with one NP query. Here the class ZPP^{NP[1]} has the property that generalizing it in the slightest ways would make it contain AM intersect coAM, for which it is notoriously open to prove any explicit lower bounds. We also prove that US !subseteq ZPP^{NP[1]}, where US is the class whose canonically complete problem is the variant of set-disjointness where yes-instances are uniquely intersecting. We also prove that US !subseteq coDP, where DP is the class of differences of two NP sets. Finally, we explore an intriguing open issue: are rank-1 matrices inherently more powerful than rectangles in communication complexity? We prove a new separation concerning PP that sheds light on this issue and strengthens some previously known separations.
Cite as

Mika Göös, Toniann Pitassi, and Thomas Watson. The Landscape of Communication Complexity Classes. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 86:1-86:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{goos_et_al:LIPIcs.ICALP.2016.86,
  author =	{G\"{o}\"{o}s, Mika and Pitassi, Toniann and Watson, Thomas},
  title =	{{The Landscape of Communication Complexity Classes}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{86:1--86:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.86},
  URN =		{urn:nbn:de:0030-drops-61990},
  doi =		{10.4230/LIPIcs.ICALP.2016.86},
  annote =	{Keywords: Landscape, communication, complexity, classes}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.721
Communication Complexity of Set-Disjointness for All Probabilities

Authors: Mika Göös and Thomas Watson

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Abstract
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 alpha and beta, and a near-complete characterization for public-coin protocols. In particular, we obtain a simple proof of a theorem of Braverman and Moitra (STOC 2013), who studied the case where alpha=1/2+epsilon(n) and beta=1/2-epsilon(n). The following contributions play a crucial role in our characterization and are interesting in their own right. (1) We introduce two communication analogues of the classical complexity class that captures small bounded-error computations: we define a "restricted" class SBP (which lies between MA and AM) and an "unrestricted" class USBP. The distinction between them is analogous to the distinction between the well-known communication classes PP and UPP. (2) We show that the SBP communication complexity is precisely captured by the classical corruption lower bound method. This sharpens a theorem of Klauck (CCC 2003). (3) We use information complexity arguments to prove a linear lower bound on the USBP complexity of set-disjointness.
Cite as

Mika Göös and Thomas Watson. Communication Complexity of Set-Disjointness for All Probabilities. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 721-736, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{goos_et_al:LIPIcs.APPROX-RANDOM.2014.721,
  author =	{G\"{o}\"{o}s, Mika and Watson, Thomas},
  title =	{{Communication Complexity of Set-Disjointness for All Probabilities}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{721--736},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.721},
  URN =		{urn:nbn:de:0030-drops-47342},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.721},
  annote =	{Keywords: Communication Complexity, Set-Disjointness, All Probabilities}
}
Document
DOI: 10.4230/LIPIcs.STACS.2014.663
The Complexity of Deciding Statistical Properties of Samplable Distributions

Authors: Thomas Watson

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Abstract
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 these problems are C_{=P}-complete, by showing that the following promise problem (which is a restriction of all the above problems) is C_{=P}-complete: Given a circuit, distinguish the case where the output distribution is uniform and the case where every pair of coordinates is neither uncorrelated nor identically distributed. This completeness result holds even for samplers that are depth-3 circuits. We also consider circuits that are d-local, in the sense that each output bit depends on at most d input bits. We give linear-time algorithms for deciding whether a 2-local sampler's joint distribution is fully independent, and whether it is exchangeable. We also show that for general circuits, certain approximation versions of the problems of deciding full independence and exchangeability are SZK-complete. We also introduce a bounded-error version of C_{=P}, which we call BC_{=P}, and we investigate its structural properties.
Cite as

Thomas Watson. The Complexity of Deciding Statistical Properties of Samplable Distributions. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 663-674, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{watson:LIPIcs.STACS.2014.663,
  author =	{Watson, Thomas},
  title =	{{The Complexity of Deciding Statistical Properties of Samplable Distributions}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{663--674},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.663},
  URN =		{urn:nbn:de:0030-drops-44960},
  doi =		{10.4230/LIPIcs.STACS.2014.663},
  annote =	{Keywords: Complexity, statistical properties, samplable distributions}
}
Document
DOI: 10.4230/LIPIcs.STACS.2013.634
Advice Lower Bounds for the Dense Model Theorem

Authors: Thomas Watson

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Abstract
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 epsilon'-indistinguishable from uniform, there exists a "dense model" for D, that is, a distribution that is delta-dense in the uniform distribution and is epsilon-indistinguishable from D. This epsilon-indistinguishability is with respect to an arbitrary small class of functions F. For the natural case where epsilon' >= Omega(epsilon delta) and epsilon >= delta^{O(1)}, our lower bound implies that Omega(sqrt{(1/epsilon)log(1/delta)} log|F|) advice bits are necessary. There is only a polynomial gap between our lower bound and the best upper bound for this case (due to Zhang), which is O((1/epsilon^2)log(1/delta) log|F|). Our lower bound can be viewed as an analog of list size lower bounds for list-decoding of error-correcting codes, but for "dense model decoding" instead. Our proof introduces some new techniques which may be of independent interest, including an analysis of a majority of majorities of p-biased bits. The latter analysis uses an extremely tight lower bound on the tail of the binomial distribution, which we could not find in the literature.
Cite as

Thomas Watson. Advice Lower Bounds for the Dense Model Theorem. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 634-645, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{watson:LIPIcs.STACS.2013.634,
  author =	{Watson, Thomas},
  title =	{{Advice Lower Bounds for the Dense Model Theorem}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{634--645},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.634},
  URN =		{urn:nbn:de:0030-drops-39717},
  doi =		{10.4230/LIPIcs.STACS.2013.634},
  annote =	{Keywords: Pseudorandomness, advice lower bounds, dense model theorem}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact