Search Results

Documents authored by Buhrman, Harry

Document
DOI: 10.4230/LIPIcs.ITCS.2024.1
A Qubit, a Coin, and an Advice String Walk into a Relational Problem

Authors: Scott Aaronson, Harry Buhrman, and William Kretschmer

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
Relational problems (those with many possible valid outputs) are different from decision problems, but it is easy to forget just how different. This paper initiates the study of FBQP/qpoly, the class of relational problems solvable in quantum polynomial-time with the help of polynomial-sized quantum advice, along with its analogues for deterministic and randomized computation (FP, FBPP) and advice (/poly, /rpoly). Our first result is that FBQP/qpoly ≠ FBQP/poly, unconditionally, with no oracle - a striking contrast with what we know about the analogous decision classes. The proof repurposes the separation between quantum and classical one-way communication complexities due to Bar-Yossef, Jayram, and Kerenidis. We discuss how this separation raises the prospect of near-term experiments to demonstrate "quantum information supremacy," a form of quantum supremacy that would not depend on unproved complexity assumptions. Our second result is that FBPP ̸ ⊂ FP/poly - that is, Adleman’s Theorem fails for relational problems - unless PSPACE ⊂ NP/poly. Our proof uses IP = PSPACE and time-bounded Kolmogorov complexity. On the other hand, we show that proving FBPP ̸ ⊂ FP/poly will be hard, as it implies a superpolynomial circuit lower bound for PromiseBPEXP. We prove the following further results: - Unconditionally, FP ≠ FBPP and FP/poly ≠ FBPP/poly (even when these classes are carefully defined). - FBPP/poly = FBPP/rpoly (and likewise for FBQP). For sampling problems, by contrast, SampBPP/poly ≠ SampBPP/rpoly (and likewise for SampBQP).
Cite as

Scott Aaronson, Harry Buhrman, and William Kretschmer. A Qubit, a Coin, and an Advice String Walk into a Relational Problem. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 1:1-1:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{aaronson_et_al:LIPIcs.ITCS.2024.1,
  author =	{Aaronson, Scott and Buhrman, Harry and Kretschmer, William},
  title =	{{A Qubit, a Coin, and an Advice String Walk into a Relational Problem}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{1:1--1:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.1},
  URN =		{urn:nbn:de:0030-drops-195290},
  doi =		{10.4230/LIPIcs.ITCS.2024.1},
  annote =	{Keywords: Relational problems, quantum advice, randomized advice, FBQP, FBPP}
}
Document
Extended Abstract
DOI: 10.4230/LIPIcs.ITCS.2024.21
Noisy Decoding by Shallow Circuits with Parities: Classical and Quantum (Extended Abstract)

Authors: Jop Briët, Harry Buhrman, Davi Castro-Silva, and Niels M. P. Neumann

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
We consider the problem of decoding corrupted error correcting codes with NC⁰[⊕] circuits in the classical and quantum settings. We show that any such classical circuit can correctly recover only a vanishingly small fraction of messages, if the codewords are sent over a noisy channel with positive error rate. Previously this was known only for linear codes with large dual distance, whereas our result applies to any code. By contrast, we give a simple quantum circuit that correctly decodes the Hadamard code with probability Ω(ε²) even if a (1/2 - ε)-fraction of a codeword is adversarially corrupted. Our classical hardness result is based on an equidistribution phenomenon for multivariate polynomials over a finite field under biased input-distributions. This is proved using a structure-versus-randomness strategy based on a new notion of rank for high-dimensional polynomial maps that may be of independent interest. Our quantum circuit is inspired by a non-local version of the Bernstein-Vazirani problem, a technique to generate "poor man’s cat states" by Watts et al., and a constant-depth quantum circuit for the OR function by Takahashi and Tani.
Cite as

Jop Briët, Harry Buhrman, Davi Castro-Silva, and Niels M. P. Neumann. Noisy Decoding by Shallow Circuits with Parities: Classical and Quantum (Extended Abstract). In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 21:1-21:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{briet_et_al:LIPIcs.ITCS.2024.21,
  author =	{Bri\"{e}t, Jop and Buhrman, Harry and Castro-Silva, Davi and Neumann, Niels M. P.},
  title =	{{Noisy Decoding by Shallow Circuits with Parities: Classical and Quantum (Extended Abstract)}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{21:1--21:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.21},
  URN =		{urn:nbn:de:0030-drops-195490},
  doi =		{10.4230/LIPIcs.ITCS.2024.21},
  annote =	{Keywords: Coding theory, circuit complexity, quantum complexity theory, higher-order Fourier analysis, non-local games}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.29
Quantum Majority Vote

Authors: Harry Buhrman, Noah Linden, Laura Mančinska, Ashley Montanaro, and Maris Ozols

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
Majority vote is a basic method for amplifying correct outcomes that is widely used in computer science and beyond. While it can amplify the correctness of a quantum device with classical output, the analogous procedure for quantum output is not known. We introduce quantum majority vote as the following task: given a product state |ψ_1⟩ ⊗ … ⊗ |ψ_n⟩ where each qubit is in one of two orthogonal states |ψ⟩ or |ψ^⟂⟩, output the majority state. We show that an optimal algorithm for this problem achieves worst-case fidelity of 1/2 + Θ(1/√n). Under the promise that at least 2/3 of the input qubits are in the majority state, the fidelity increases to 1 - Θ(1/n) and approaches 1 as n increases. We also consider the more general problem of computing any symmetric and equivariant Boolean function f: {0,1}ⁿ → {0,1} in an unknown quantum basis, and show that a generalization of our quantum majority vote algorithm is optimal for this task. The optimal parameters for the generalized algorithm and its worst-case fidelity can be determined by a simple linear program of size O(n). The time complexity of the algorithm is O(n⁴ log n) where n is the number of input qubits.
Cite as

Harry Buhrman, Noah Linden, Laura Mančinska, Ashley Montanaro, and Maris Ozols. Quantum Majority Vote. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, p. 29:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{buhrman_et_al:LIPIcs.ITCS.2023.29,
  author =	{Buhrman, Harry and Linden, Noah and Man\v{c}inska, Laura and Montanaro, Ashley and Ozols, Maris},
  title =	{{Quantum Majority Vote}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{29:1--29:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.29},
  URN =		{urn:nbn:de:0030-drops-175321},
  doi =		{10.4230/LIPIcs.ITCS.2023.29},
  annote =	{Keywords: quantum algorithms, quantum majority vote, Schur-Weyl duality}
}
Document
DOI: 10.4230/LIPIcs.TQC.2022.10
Memory Compression with Quantum Random-Access Gates

Authors: Harry Buhrman, Bruno Loff, Subhasree Patro, and Florian Speelman

Published in: LIPIcs, Volume 232, 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)

Abstract
In the classical RAM, we have the following useful property. If we have an algorithm that uses M memory cells throughout its execution, and in addition is sparse, in the sense that, at any point in time, only m out of M cells will be non-zero, then we may "compress" it into another algorithm which uses only m log M memory and runs in almost the same time. We may do so by simulating the memory using either a hash table, or a self-balancing tree. We show an analogous result for quantum algorithms equipped with quantum random-access gates. If we have a quantum algorithm that runs in time T and uses M qubits, such that the state of the memory, at any time step, is supported on computational-basis vectors of Hamming weight at most m, then it can be simulated by another algorithm which uses only O(m log M) memory, and runs in time Õ(T). We show how this theorem can be used, in a black-box way, to simplify the presentation in several papers. Broadly speaking, when there exists a need for a space-efficient history-independent quantum data-structure, it is often possible to construct a space-inefficient, yet sparse, quantum data structure, and then appeal to our main theorem. This results in simpler and shorter arguments.
Cite as

Harry Buhrman, Bruno Loff, Subhasree Patro, and Florian Speelman. Memory Compression with Quantum Random-Access Gates. In 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 232, pp. 10:1-10:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{buhrman_et_al:LIPIcs.TQC.2022.10,
  author =	{Buhrman, Harry and Loff, Bruno and Patro, Subhasree and Speelman, Florian},
  title =	{{Memory Compression with Quantum Random-Access Gates}},
  booktitle =	{17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)},
  pages =	{10:1--10:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-237-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{232},
  editor =	{Le Gall, Fran\c{c}ois and Morimae, Tomoyuki},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2022.10},
  URN =		{urn:nbn:de:0030-drops-165177},
  doi =		{10.4230/LIPIcs.TQC.2022.10},
  annote =	{Keywords: complexity theory, data structures, algorithms, quantum walk}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.31
Limits of Quantum Speed-Ups for Computational Geometry and Other Problems: Fine-Grained Complexity via Quantum Walks

Authors: Harry Buhrman, Bruno Loff, Subhasree Patro, and Florian Speelman

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
Many computational problems are subject to a quantum speed-up: one might find that a problem having an O(n³)-time or O(n²)-time classic algorithm can be solved by a known O(n^{1.5})-time or O(n)-time quantum algorithm. The question naturally arises: how much quantum speed-up is possible? The area of fine-grained complexity allows us to prove optimal lower-bounds on the complexity of various computational problems, based on the conjectured hardness of certain natural, well-studied problems. This theory has recently been extended to the quantum setting, in two independent papers by Buhrman, Patro and Speelman [Buhrman et al., 2021], and by Aaronson, Chia, Lin, Wang, and Zhang [Aaronson et al., 2020]. In this paper, we further extend the theory of fine-grained complexity to the quantum setting. A fundamental conjecture in the classical setting states that the 3SUM problem cannot be solved by (classical) algorithms in time O(n^{2-ε}), for any ε > 0. We formulate an analogous conjecture, the Quantum-3SUM-Conjecture, which states that there exist no sublinear O(n^{1-ε})-time quantum algorithms for the 3SUM problem. Based on the Quantum-3SUM-Conjecture, we show new lower-bounds on the time complexity of quantum algorithms for several computational problems. Most of our lower-bounds are optimal, in that they match known upper-bounds, and hence they imply tight limits on the quantum speedup that is possible for these problems. These results are proven by adapting to the quantum setting known classical fine-grained reductions from the 3SUM problem. This adaptation is not trivial, however, since the original classical reductions require pre-processing the input in various ways, e.g. by sorting it according to some order, and this pre-processing (provably) cannot be done in sublinear quantum time. We overcome this bottleneck by combining a quantum walk with a classical dynamic data-structure having a certain "history-independence" property. This type of construction has been used in the past to prove upper bounds, and here we use it for the first time as part of a reduction. This general proof strategy allows us to prove tight lower bounds on several computational-geometry problems, on Convolution-3SUM and on the 0-Edge-Weight-Triangle problem, conditional on the Quantum-3SUM-Conjecture. We believe this proof strategy will be useful in proving tight (conditional) lower-bounds, and limits on quantum speed-ups, for many other problems.
Cite as

Harry Buhrman, Bruno Loff, Subhasree Patro, and Florian Speelman. Limits of Quantum Speed-Ups for Computational Geometry and Other Problems: Fine-Grained Complexity via Quantum Walks. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 31:1-31:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{buhrman_et_al:LIPIcs.ITCS.2022.31,
  author =	{Buhrman, Harry and Loff, Bruno and Patro, Subhasree and Speelman, Florian},
  title =	{{Limits of Quantum Speed-Ups for Computational Geometry and Other Problems: Fine-Grained Complexity via Quantum Walks}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{31:1--31:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.31},
  URN =		{urn:nbn:de:0030-drops-156273},
  doi =		{10.4230/LIPIcs.ITCS.2022.31},
  annote =	{Keywords: complexity theory, fine-grained complexity, 3SUM, computational geometry problems, data structures, quantum walk}
}
Document
DOI: 10.4230/LIPIcs.STACS.2021.19
A Framework of Quantum Strong Exponential-Time Hypotheses

Authors: Harry Buhrman, Subhasree Patro, and Florian Speelman

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

Abstract
The strong exponential-time hypothesis (SETH) is a commonly used conjecture in the field of complexity theory. It essentially states that determining whether a CNF formula is satisfiable can not be done faster than exhaustive search over all possible assignments. This hypothesis and its variants gave rise to a fruitful field of research, fine-grained complexity, obtaining (mostly tight) lower bounds for many problems in P whose unconditional lower bounds are very likely beyond current techniques. In this work, we introduce an extensive framework of Quantum Strong Exponential-Time Hypotheses, as quantum analogues to what SETH is for classical computation. Using the QSETH framework, we are able to translate quantum query lower bounds on black-box problems to conditional quantum time lower bounds for many problems in P. As an example, we provide a conditional quantum time lower bound of Ω(n^1.5) for the Longest Common Subsequence and Edit Distance problems. We also show that the n² SETH-based lower bound for a recent scheme for Proofs of Useful Work carries over to the quantum setting using our framework, maintaining a quadratic gap between verifier and prover. Lastly, we show that the assumptions in our framework can not be simplified further with relativizing proof techniques, as they are false in relativized worlds.
Cite as

Harry Buhrman, Subhasree Patro, and Florian Speelman. A Framework of Quantum Strong Exponential-Time Hypotheses. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 19:1-19:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{buhrman_et_al:LIPIcs.STACS.2021.19,
  author =	{Buhrman, Harry and Patro, Subhasree and Speelman, Florian},
  title =	{{A Framework of Quantum Strong Exponential-Time Hypotheses}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{19:1--19:19},
  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.19},
  URN =		{urn:nbn:de:0030-drops-136642},
  doi =		{10.4230/LIPIcs.STACS.2021.19},
  annote =	{Keywords: complexity theory, fine-grained complexity, longest common subsequence, edit distance, quantum query complexity, strong exponential-time hypothesis}
}
Document
DOI: 10.4230/LIPIcs.STACS.2019.12
Bounding Quantum-Classical Separations for Classes of Nonlocal Games

Authors: Tom Bannink, Jop Briët, Harry Buhrman, Farrokh Labib, and Troy Lee

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

Abstract
We bound separations between the entangled and classical values for several classes of nonlocal t-player games. Our motivating question is whether there is a family of t-player XOR games for which the entangled bias is 1 but for which the classical bias goes down to 0, for fixed t. Answering this question would have important consequences in the study of multi-party communication complexity, as a positive answer would imply an unbounded separation between randomized communication complexity with and without entanglement. Our contribution to answering the question is identifying several general classes of games for which the classical bias can not go to zero when the entangled bias stays above a constant threshold. This rules out the possibility of using these games to answer our motivating question. A previously studied set of XOR games, known not to give a positive answer to the question, are those for which there is a quantum strategy that attains value 1 using a so-called Schmidt state. We generalize this class to mod-m games and show that their classical value is always at least 1/m + (m-1)/m t^{1-t}. Secondly, for free XOR games, in which the input distribution is of product form, we show beta(G) >= beta^*(G)^{2^t} where beta(G) and beta^*(G) are the classical and entangled biases of the game respectively. We also introduce so-called line games, an example of which is a slight modification of the Magic Square game, and show that they can not give a positive answer to the question either. Finally we look at two-player unique games and show that if the entangled value is 1-epsilon then the classical value is at least 1-O(sqrt{epsilon log k}) where k is the number of outputs in the game. Our proofs use semidefinite-programming techniques, the Gowers inverse theorem and hypergraph norms.
Cite as

Tom Bannink, Jop Briët, Harry Buhrman, Farrokh Labib, and Troy Lee. Bounding Quantum-Classical Separations for Classes of Nonlocal Games. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 12:1-12:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bannink_et_al:LIPIcs.STACS.2019.12,
  author =	{Bannink, Tom and Bri\"{e}t, Jop and Buhrman, Harry and Labib, Farrokh and Lee, Troy},
  title =	{{Bounding Quantum-Classical Separations for Classes of Nonlocal Games}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{12:1--12:11},
  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.12},
  URN =		{urn:nbn:de:0030-drops-102512},
  doi =		{10.4230/LIPIcs.STACS.2019.12},
  annote =	{Keywords: Nonlocal games, communication complexity, bounded separations, semidefinite programming, pseudorandomness, Gowers norms}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2017.24
Nondeterministic Quantum Communication Complexity: the Cyclic Equality Game and Iterated Matrix Multiplication

Authors: Harry Buhrman, Matthias Christandl, and Jeroen Zuiddam

Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)

Abstract
We study nondeterministic multiparty quantum communication with a quantum generalization of broadcasts. We show that, with number-in-hand classical inputs, the communication complexity of a Boolean function in this communication model equals the logarithm of the support rank of the corresponding tensor, whereas the approximation complexity in this model equals the logarithm of the border support rank. This characterisation allows us to prove a log-rank conjecture posed by Villagra et al. for nondeterministic multiparty quantum communication with message passing. The support rank characterization of the communication model connects quantum communication complexity intimately to the theory of asymptotic entanglement transformation and algebraic complexity theory. In this context, we introduce the graphwise equality problem. For a cycle graph, the complexity of this communication problem is closely related to the complexity of the computational problem of multiplying matrices, or more precisely, it equals the logarithm of the support rank of the iterated matrix multiplication tensor. We employ Strassen’s laser method to show that asymptotically there exist nontrivial protocols for every odd-player cyclic equality problem. We exhibit an efficient protocol for the 5-player problem for small inputs, and we show how Young flattenings yield nontrivial complexity lower bounds.
Cite as

Harry Buhrman, Matthias Christandl, and Jeroen Zuiddam. Nondeterministic Quantum Communication Complexity: the Cyclic Equality Game and Iterated Matrix Multiplication. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 24:1-24:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{buhrman_et_al:LIPIcs.ITCS.2017.24,
  author =	{Buhrman, Harry and Christandl, Matthias and Zuiddam, Jeroen},
  title =	{{Nondeterministic Quantum Communication Complexity: the Cyclic Equality Game and Iterated Matrix Multiplication}},
  booktitle =	{8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
  pages =	{24:1--24:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-029-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{67},
  editor =	{Papadimitriou, Christos H.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.24},
  URN =		{urn:nbn:de:0030-drops-81812},
  doi =		{10.4230/LIPIcs.ITCS.2017.24},
  annote =	{Keywords: quantum communication complexity, broadcast channel, number-in-hand, matrix multiplication, support rank}
}
Document
DOI: 10.4230/LIPIcs.STACS.2016.24
Catalytic Space: Non-determinism and Hierarchy

Authors: Harry Buhrman, Michal Koucký, Bruno Loff, and Florian Speelman

Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)

Abstract
Catalytic computation, defined by Buhrman, Cleve, Koucký, Loff and Speelman (STOC 2014), is a space-bounded computation where in addition to our working memory we have an exponentially larger auxiliary memory which is full; the auxiliary memory may be used throughout the computation, but it must be restored to its initial content by the end of the computation. Motivated by the surprising power of this model, we set out to study the non-deterministic version of catalytic computation. We establish that non-deterministic catalytic log-space is contained in ZPP, which is the same bound known for its deterministic counterpart, and we prove that non-deterministic catalytic space is closed under complement (under a standard derandomization assumption). Furthermore, we establish hierarchy theorems for non-deterministic and deterministic catalytic computation.
Cite as

Harry Buhrman, Michal Koucký, Bruno Loff, and Florian Speelman. Catalytic Space: Non-determinism and Hierarchy. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 24:1-24:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{buhrman_et_al:LIPIcs.STACS.2016.24,
  author =	{Buhrman, Harry and Kouck\'{y}, Michal and Loff, Bruno and Speelman, Florian},
  title =	{{Catalytic Space: Non-determinism and Hierarchy}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{24:1--24:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Ollinger, Nicolas and Vollmer, Heribert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.24},
  URN =		{urn:nbn:de:0030-drops-57258},
  doi =		{10.4230/LIPIcs.STACS.2016.24},
  annote =	{Keywords: catalytic computation, Immerman–Szelepcs\'{e}nyi theorem, space hierarchy}
}
Document
DOI: 10.4230/LIPIcs.TQC.2015.206
Round Elimination in Exact Communication Complexity

Authors: Jop Briët, Harry Buhrman, Debbie Leung, Teresa Piovesan, and Florian Speelman

Published in: LIPIcs, Volume 44, 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)

Abstract
We study two basic graph parameters, the chromatic number and the orthogonal rank, in the context of classical and quantum exact communication complexity. In particular, we consider two types of communication problems that we call promise equality and list problems. For both of these, it was already known that the one-round classical and one-round quantum complexities are characterized by the chromatic number and orthogonal rank of a certain graph, respectively. In a promise equality problem, Alice and Bob must decide if their inputs are equal or not. We prove that classical protocols for such problems can always be reduced to one-round protocols with no extra communication. In contrast, we give an explicit instance of a promise problem that exhibits an exponential gap between the one- and two-round exact quantum communication complexities. Whereas the chromatic number thus captures the complete complexity of promise equality problems, the hierarchy of "quantum chromatic numbers" (starting with the orthogonal rank) giving the quantum communication complexity for every fixed number of communication rounds thus turns out to enjoy a much richer structure. In a list problem, Bob gets a subset of some finite universe, Alice gets an element from Bob's subset, and their goal is for Bob to learn which element Alice was given. The best general lower bound (due to Orlitsky) and upper bound (due to Naor, Orlitsky, and Shor) on the classical communication complexity of such problems differ only by a constant factor. We exhibit an example showing that, somewhat surprisingly, the four-round protocol used in the bound of Naor et al. can in fact be optimal. Finally, we pose a conjecture on the orthogonality rank of a certain graph whose truth would imply an intriguing impossibility of round elimination in quantum protocols for list problems, something that works trivially in the classical case.
Cite as

Jop Briët, Harry Buhrman, Debbie Leung, Teresa Piovesan, and Florian Speelman. Round Elimination in Exact Communication Complexity. In 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 44, pp. 206-225, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{briet_et_al:LIPIcs.TQC.2015.206,
  author =	{Bri\"{e}t, Jop and Buhrman, Harry and Leung, Debbie and Piovesan, Teresa and Speelman, Florian},
  title =	{{Round Elimination in Exact Communication Complexity}},
  booktitle =	{10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)},
  pages =	{206--225},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-96-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{44},
  editor =	{Beigi, Salman and K\"{o}nig, Robert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2015.206},
  URN =		{urn:nbn:de:0030-drops-55588},
  doi =		{10.4230/LIPIcs.TQC.2015.206},
  annote =	{Keywords: communication complexity, round elimination, quantum communication, protocols, chromatic numbers}
}
Document
DOI: 10.4230/LIPIcs.TQC.2014.24
On the Parallel Repetition of Multi-Player Games: The No-Signaling Case

Authors: Harry Buhrman, Serge Fehr, and Christian Schaffner

Published in: LIPIcs, Volume 27, 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)

Abstract
We consider the natural extension of two-player nonlocal games to an arbitrary number of players. An important question for such nonlocal games is their behavior under parallel repetition. For two-player nonlocal games, it is known that both the classical and the non-signaling value of any game converges to zero exponentially fast under parallel repetition, given that the game is non-trivial to start with (i.e., has classical/non-signaling value < 1). Very recent results show similar behavior of the quantum value of a two-player game under parallel repetition. For nonlocal games with three or more players, very little is known up to present on their behavior under parallel repetition; this is true for the classical, the quantum and the non-signaling value. In this work, we show a parallel repetition theorem for the non-signaling value of a large class of multi-player games, for an arbitrary number of players. Our result applies to all multi-player games for which all possible combinations of questions have positive probability; this class in particular includes all free games, in which the questions to the players are chosen independently. Specifically, we prove that if the original game G has a non-signaling value v_{ns}(G) < 1, then the non-signaling value of the n-fold parallel repetition is exponentially small in n. Stronger than that, we prove that the probability of winning more than (v_{ns}(G) + delta) * n parallel repetitions is exponentially small in n (for any delta > 0). Our parallel repetition theorem for multi-player games is weaker than the known parallel repetition results for two-player games in that the rate at which the non-signaling value of the game decreases not only depends on the non-signaling value of the original game (and the number of possible responses), but on the complete description of the game. Nevertheless, we feel that our result is a first step towards a better understanding of the parallel repetition of nonlocal games with more than two players.
Cite as

Harry Buhrman, Serge Fehr, and Christian Schaffner. On the Parallel Repetition of Multi-Player Games: The No-Signaling Case. In 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 27, pp. 24-35, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{buhrman_et_al:LIPIcs.TQC.2014.24,
  author =	{Buhrman, Harry and Fehr, Serge and Schaffner, Christian},
  title =	{{On the Parallel Repetition of Multi-Player Games: The No-Signaling Case}},
  booktitle =	{9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014)},
  pages =	{24--35},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-73-6},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{27},
  editor =	{Flammia, Steven T. and Harrow, Aram W.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2014.24},
  URN =		{urn:nbn:de:0030-drops-48034},
  doi =		{10.4230/LIPIcs.TQC.2014.24},
  annote =	{Keywords: Parallel repetition, non-signaling value, multi-player non-local games}
}
Document
DOI: 10.4230/DagSemProc.09421.5
Learning Parities in the Mistake-Bound model

Authors: Harry Buhrman, David Garcia-Soriano, and Arie Matsliah

Published in: Dagstuhl Seminar Proceedings, Volume 9421, Algebraic Methods in Computational Complexity (2010)

Abstract
We study the problem of learning parity functions that depend on at most $k$ variables ($k$-parities) attribute-efficiently in the mistake-bound model. We design a simple, deterministic, polynomial-time algorithm for learning $k$-parities with mistake bound $O(n^{1-frac{c}{k}})$, for any constant $c > 0$. This is the first polynomial-time algorithms that learns $omega(1)$-parities in the mistake-bound model with mistake bound $o(n)$. Using the standard conversion techniques from the mistake-bound model to the PAC model, our algorithm can also be used for learning $k$-parities in the PAC model. In particular, this implies a slight improvement on the results of Klivans and Servedio cite{rocco} for learning $k$-parities in the PAC model. We also show that the $widetilde{O}(n^{k/2})$ time algorithm from cite{rocco} that PAC-learns $k$-parities with optimal sample complexity can be extended to the mistake-bound model.
Cite as

Harry Buhrman, David Garcia-Soriano, and Arie Matsliah. Learning Parities in the Mistake-Bound model. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 9421, pp. 1-9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{buhrman_et_al:DagSemProc.09421.5,
  author =	{Buhrman, Harry and Garcia-Soriano, David and Matsliah, Arie},
  title =	{{Learning Parities in the Mistake-Bound model}},
  booktitle =	{Algebraic Methods in Computational Complexity},
  pages =	{1--9},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9421},
  editor =	{Manindra Agrawal and Lance Fortnow and Thomas Thierauf and Christopher Umans},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09421.5},
  URN =		{urn:nbn:de:0030-drops-24178},
  doi =		{10.4230/DagSemProc.09421.5},
  annote =	{Keywords: Attribute-efficient learning, parities, mistake-bound}
}
Document
DOI: 10.4230/DagSemProc.09421.8
Unconditional Lower Bounds against Advice

Authors: Harry Buhrman, Lance Fortnow, and Rahul Santhanam

Published in: Dagstuhl Seminar Proceedings, Volume 9421, Algebraic Methods in Computational Complexity (2010)

Abstract
We show several unconditional lower bounds for exponential time classes against polynomial time classes with advice, including: (1) For any constant c, NEXP not in P^{NP[n^c]} (2) For any constant c, MAEXP not in MA/n^c (3) BPEXP not in BPP/n^{o(1)}. It was previously unknown even whether NEXP in NP/n^{0.01}. For the probabilistic classes, no lower bounds for uniform exponential time against advice were known before. We also consider the question of whether these lower bounds can be made to work on almost all input lengths rather than on infinitely many. We give an oracle relative to which NEXP in i.o.NP, which provides evidence that this is not possible with current techniques.
Cite as

Harry Buhrman, Lance Fortnow, and Rahul Santhanam. Unconditional Lower Bounds against Advice. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 9421, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{buhrman_et_al:DagSemProc.09421.8,
  author =	{Buhrman, Harry and Fortnow, Lance and Santhanam, Rahul},
  title =	{{Unconditional Lower Bounds against Advice}},
  booktitle =	{Algebraic Methods in Computational Complexity},
  pages =	{1--11},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9421},
  editor =	{Manindra Agrawal and Lance Fortnow and Thomas Thierauf and Christopher Umans},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09421.8},
  URN =		{urn:nbn:de:0030-drops-24112},
  doi =		{10.4230/DagSemProc.09421.8},
  annote =	{Keywords: Advice, derandomization, diagonalization, lower bounds, semantic classes}
}
Document
DOI: 10.4230/DagSemProc.07411.5
High Entropy Random Selection Protocols

Authors: Nikolai K. Vereshchagin, Harry Buhrman, Matthias Cristandl, Michal Koucky, Zvi Lotker, and Boaz Patt-Shamir

Published in: Dagstuhl Seminar Proceedings, Volume 7411, Algebraic Methods in Computational Complexity (2008)

Abstract
We study the two party problem of randomly selecting a string among all the strings of length n. We want the protocol to have the property that the output distribution has high entropy, even when one of the two parties is dishonest and deviates from the protocol. We develop protocols that achieve high, close to n, entropy. In the literature the randomness guarantee is usually expressed as being close to the uniform distribution or in terms of resiliency. The notion of entropy is not directly comparable to that of resiliency, but we establish a connection between the two that allows us to compare our protocols with the existing ones. We construct an explicit protocol that yields entropy n - O(1) and has 4log^* n rounds, improving over the protocol of Goldwasser et al. that also achieves this entropy but needs O(n) rounds. Both these protocols need O(n^2) bits of communication. Next we reduce the communication in our protocols. We show the existence, non-explicitly, of a protocol that has 6-rounds, 2n + 8log n bits of communication and yields entropy n- O(log n) and min-entropy n/2 - O(log n). Our protocol achieves the same entropy bound as the recent, also non-explicit, protocol of Gradwohl et al., however achieves much higher min-entropy: n/2 - O(log n) versus O(log n). Finally we exhibit very simple explicit protocols. We connect the security parameter of these geometric protocols with the well studied Kakeya problem motivated by harmonic analysis and analytical number theory. We are only able to prove that these protocols have entropy 3n/4 but still n/2 - O(log n) min-entropy. Therefore they do not perform as well with respect to the explicit constructions of Gradwohl et al. entropy-wise, but still have much better min-entropy. We conjecture that these simple protocols achieve n -o(n) entropy. Our geometric construction and its relation to the Kakeya problem follows a new and different approach to the random selection problem than any of the previously known protocols.
Cite as

Nikolai K. Vereshchagin, Harry Buhrman, Matthias Cristandl, Michal Koucky, Zvi Lotker, and Boaz Patt-Shamir. High Entropy Random Selection Protocols. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 7411, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{vereshchagin_et_al:DagSemProc.07411.5,
  author =	{Vereshchagin, Nikolai K. and Buhrman, Harry and Cristandl, Matthias and Koucky, Michal and Lotker, Zvi and Patt-Shamir, Boaz},
  title =	{{High Entropy Random Selection Protocols}},
  booktitle =	{Algebraic Methods in Computational Complexity},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7411},
  editor =	{Manindra Agrawal and Harry Buhrman and Lance Fortnow and Thomas Thierauf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07411.5},
  URN =		{urn:nbn:de:0030-drops-13091},
  doi =		{10.4230/DagSemProc.07411.5},
  annote =	{Keywords: Shannon entropy, Random string ds}
}
Document
DOI: 10.4230/DagSemProc.07411.1
07411 Abstracts Collection – Algebraic Methods in Computational Complexity

Authors: Manindra Agrawal, Harry Buhrman, Lance Fortnow, and Thomas Thierauf

Published in: Dagstuhl Seminar Proceedings, Volume 7411, Algebraic Methods in Computational Complexity (2008)

Abstract
From 07.10. to 12.10., the Dagstuhl Seminar 07411 ``Algebraic Methods in Computational Complexity'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Manindra Agrawal, Harry Buhrman, Lance Fortnow, and Thomas Thierauf. 07411 Abstracts Collection – Algebraic Methods in Computational Complexity. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 7411, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:DagSemProc.07411.1,
  author =	{Agrawal, Manindra and Buhrman, Harry and Fortnow, Lance and Thierauf, Thomas},
  title =	{{07411 Abstracts Collection – Algebraic Methods in Computational Complexity}},
  booktitle =	{Algebraic Methods in Computational Complexity},
  pages =	{1--13},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7411},
  editor =	{Manindra Agrawal and Harry Buhrman and Lance Fortnow and Thomas Thierauf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07411.1},
  URN =		{urn:nbn:de:0030-drops-13072},
  doi =		{10.4230/DagSemProc.07411.1},
  annote =	{Keywords: Computational complexity, algebra, quantum computing, (de-) randomization}
}
Document
DOI: 10.4230/DagSemProc.07411.2
07411 Executive Summary – Algebraic Methods in Computational Complexity

Authors: Manindra Agrawal, Harry Buhrman, Lance Fortnow, and Thomas Thierauf

Published in: Dagstuhl Seminar Proceedings, Volume 7411, Algebraic Methods in Computational Complexity (2008)

Abstract
The seminar brought together almost 50 researchers covering a wide spectrum of complexity theory. The focus on algebraic methods showed once again the great importance of algebraic techniques for theoretical computer science. We had almost 30 talks of length between 15 and 45 minutes. This left enough room for discussions. We had an open problem session that was very much appreciated.
Cite as

Manindra Agrawal, Harry Buhrman, Lance Fortnow, and Thomas Thierauf. 07411 Executive Summary – Algebraic Methods in Computational Complexity. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 7411, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:DagSemProc.07411.2,
  author =	{Agrawal, Manindra and Buhrman, Harry and Fortnow, Lance and Thierauf, Thomas},
  title =	{{07411 Executive Summary – Algebraic Methods in Computational Complexity}},
  booktitle =	{Algebraic Methods in Computational Complexity},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7411},
  editor =	{Manindra Agrawal and Harry Buhrman and Lance Fortnow and Thomas Thierauf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07411.2},
  URN =		{urn:nbn:de:0030-drops-13061},
  doi =		{10.4230/DagSemProc.07411.2},
  annote =	{Keywords: Computational complexity, algebra, quantum computing, (de-) randomization}
}
Document
DOI: 10.4230/DagSemProc.04421.1
04421 Abstracts Collection – Algebraic Methods in Computational Complexity

Authors: Harry Buhrman, Lance Fortnow, and Thomas Thierauf

Published in: Dagstuhl Seminar Proceedings, Volume 4421, Algebraic Methods in Computational Complexity (2005)

Abstract
From 10.10.04 to 15.10.04, the Dagstuhl Seminar 04421 ``Algebraic Methods in Computational Complexity'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Harry Buhrman, Lance Fortnow, and Thomas Thierauf. 04421 Abstracts Collection – Algebraic Methods in Computational Complexity. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 4421, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{buhrman_et_al:DagSemProc.04421.1,
  author =	{Buhrman, Harry and Fortnow, Lance and Thierauf, Thomas},
  title =	{{04421 Abstracts Collection – Algebraic Methods in Computational Complexity}},
  booktitle =	{Algebraic Methods in Computational Complexity},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4421},
  editor =	{Harry Buhrman and Lance Fortnow and Thomas Thierauf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04421.1},
  URN =		{urn:nbn:de:0030-drops-1162},
  doi =		{10.4230/DagSemProc.04421.1},
  annote =	{Keywords: Computational complexity , algebraic methods , quantum computations , lower bounds}
}
Document
DOI: 10.4230/DagSemRep.357
Algebraic Methods in Quantum and Classical Models of Computation (Dagstuhl Seminar 02421)

Authors: Harry Buhrman, Lance Fortnow, and Thomas Thierauf

Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Abstract
Cite as

Harry Buhrman, Lance Fortnow, and Thomas Thierauf. Algebraic Methods in Quantum and Classical Models of Computation (Dagstuhl Seminar 02421). Dagstuhl Seminar Report 357, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2003)

Copy BibTex To Clipboard

@TechReport{buhrman_et_al:DagSemRep.357,
  author =	{Buhrman, Harry and Fortnow, Lance and Thierauf, Thomas},
  title =	{{Algebraic Methods in Quantum and Classical Models of Computation (Dagstuhl Seminar 02421)}},
  pages =	{1--16},
  ISSN =	{1619-0203},
  year =	{2003},
  type = 	{Dagstuhl Seminar Report},
  number =	{357},
  institution =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.357},
  URN =		{urn:nbn:de:0030-drops-152377},
  doi =		{10.4230/DagSemRep.357},
}
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