Thomas Watson

Proceedings of the 18th Scandinavian Symposium and Workshops on Algorithm Theory, 2022

Complexity of Fault Tolerant Query Complexity.

[BibT_eX]

[DOI]

Ramita Maharjan

Proceedings of the 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2022

2021

6-Uniform Maker-Breaker Game Is PSPACE-Complete.

[BibT_eX]

[DOI]

Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science, 2021

2020

Correction to: Communication complexity with small advantage.

[BibT_eX]

[DOI]

Comput. Complex., 2020

Tractable Unordered 3-CNF Games.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2020: Theoretical Informatics, 2020

Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity.

[BibT_eX]

[DOI]

Morgan Shirley

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

When Is Amplification Necessary for Composition in Randomized Query Complexity?

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2020

2019

A Lower Bound for Sampling Disjoint Sets.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

Correction to: Query-to-Communication Lifting for P NP.

[BibT_eX]

[DOI]

Comput. Complex., 2019

A ZPP<sup>NP[1]</sup> Lifting Theorem.

[BibT_eX]

[DOI]

Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science, 2019

Amplification with One NP Oracle Query.

[BibT_eX]

[DOI]

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

A Lower Bound for Sampling Disjoint Sets.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2019

2018

Randomized Communication versus Partition Number.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2018

Quadratic Simulations of Merlin-Arthur Games.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2018: Theoretical Informatics, 2018

Complexity of Unordered CNF Games.

[BibT_eX]

[DOI]

Proceedings of the 29th International Symposium on Algorithms and Computation, 2018

Communication Complexity with Small Advantage.

[BibT_eX]

[DOI]

Proceedings of the 33rd Computational Complexity Conference, 2018

2017

A ZPP^NP[1] Lifting Theorem.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

Randomized Communication vs. Partition Number.

[BibT_eX]

[DOI]

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Query-to-Communication Lifting for BPP.

[BibT_eX]

[DOI]

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Query-to-Communication Lifting for P^NP.

[BibT_eX]

[DOI]

Proceedings of the 32nd Computational Complexity Conference, 2017

Communication Complexity of Statistical Distance.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2017

2016

Nonnegative Rank vs. Binary Rank.

[BibT_eX]

[DOI]

Chic. J. Theor. Comput. Sci., 2016

The complexity of estimating min-entropy.

[BibT_eX]

[DOI]

Comput. Complex., 2016

The Landscape of Communication Complexity Classes.

[BibT_eX]

[DOI]

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Extension Complexity of Independent Set Polytopes.

[BibT_eX]

[DOI]

Rahul Jain

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2015

Rectangles Are Nonnegative Juntas.

[BibT_eX]

[DOI]

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Zero-Information Protocols and Unambiguity in Arthur-Merlin Communication.

[BibT_eX]

[DOI]

Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

Deterministic Communication vs. Partition Number.

[BibT_eX]

[DOI]

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014

The Complexity of Deciding Statistical Properties of Samplable Distributions.

[BibT_eX]

[DOI]

Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science, 2014

Communication Complexity of Set-Disjointness for All Probabilities.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2014

2013

The Computational Complexity of Randomness.

[BibT_eX]

[DOI]

Thomas Weir Watson

PhD thesis, 2013

Advice Lower Bounds for the Dense Model Theorem.

[BibT_eX]

[DOI]

Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

Time hierarchies for sampling distributions.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Theoretical Computer Science, 2013

2011

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

Pseudorandom Generators for Combinatorial Checkerboards.

[BibT_eX]

[DOI]

Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011

Query Complexity in Errorless Hardness Amplification.

[BibT_eX]

[DOI]

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

Extractors and Lower Bounds for Locally Samplable Sources.

[BibT_eX]

[DOI]

Anindya De

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010

Time-Space Efficient Simulations of Quantum Computations.

[BibT_eX]

[DOI]

Dieter van Melkebeek

Electron. Colloquium Comput. Complex., 2010

Relativized Worlds without Worst-Case to Average-Case Reductions for NP.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2010

2008

A Quantum Time-Space Lower Bound for the Counting Hierarchy.

[BibT_eX]

[DOI]

Dieter van Melkebeek