28 Search Results for "Fortnow, Lance"

Document
DOI: 10.4230/LIPIcs.CCC.2022.20
The Acrobatics of BQP

Authors: Scott Aaronson, DeVon Ingram, and William Kretschmer

Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)

Abstract
One can fix the randomness used by a randomized algorithm, but there is no analogous notion of fixing the quantumness used by a quantum algorithm. Underscoring this fundamental difference, we show that, in the black-box setting, the behavior of quantum polynomial-time (BQP) can be remarkably decoupled from that of classical complexity classes like NP. Specifically: - There exists an oracle relative to which NP^{BQP} ⊄ BQP^{PH}, resolving a 2005 problem of Fortnow. As a corollary, there exists an oracle relative to which 𝖯 = NP but BQP ≠ QCMA. - Conversely, there exists an oracle relative to which BQP^{NP} ⊄ PH^{BQP}. - Relative to a random oracle, PP is not contained in the "QMA hierarchy" QMA^{QMA^{QMA^{⋯}}}. - Relative to a random oracle, Σ_{k+1}^𝖯 ⊄ BQP^{Σ_k^𝖯} for every k. - There exists an oracle relative to which BQP = P^#P and yet PH is infinite. (By contrast, relative to all oracles, if NP ⊆ BPP, then PH collapses.) - There exists an oracle relative to which 𝖯 = NP ≠ BQP = 𝖯^#P. To achieve these results, we build on the 2018 achievement by Raz and Tal of an oracle relative to which BQP ⊄ PH, and associated results about the Forrelation problem. We also introduce new tools that might be of independent interest. These include a "quantum-aware" version of the random restriction method, a concentration theorem for the block sensitivity of AC⁰ circuits, and a (provable) analogue of the Aaronson-Ambainis Conjecture for sparse oracles.
Cite as

Scott Aaronson, DeVon Ingram, and William Kretschmer. The Acrobatics of BQP. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 20:1-20:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{aaronson_et_al:LIPIcs.CCC.2022.20,
  author =	{Aaronson, Scott and Ingram, DeVon and Kretschmer, William},
  title =	{{The Acrobatics of BQP}},
  booktitle =	{37th Computational Complexity Conference (CCC 2022)},
  pages =	{20:1--20:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-241-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{234},
  editor =	{Lovett, Shachar},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.20},
  URN =		{urn:nbn:de:0030-drops-165820},
  doi =		{10.4230/LIPIcs.CCC.2022.20},
  annote =	{Keywords: BQP, Forrelation, oracle separations, Polynomial Hierarchy, query complexity}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.92
Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity

Authors: Zhenjian Lu, Igor C. Oliveira, and Marius Zimand

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
The classical coding theorem in Kolmogorov complexity states that if an n-bit string x is sampled with probability δ by an algorithm with prefix-free domain then 𝖪(x) ≤ log(1/δ) + O(1). In a recent work, Lu and Oliveira [Zhenjian Lu and Igor C. Oliveira, 2021] established an unconditional time-bounded version of this result, by showing that if x can be efficiently sampled with probability δ then rKt(x) = O(log(1/δ)) + O(log n), where rKt denotes the randomized analogue of Levin’s Kt complexity. Unfortunately, this result is often insufficient when transferring applications of the classical coding theorem to the time-bounded setting, as it achieves a O(log(1/δ)) bound instead of the information-theoretic optimal log(1/δ). Motivated by this discrepancy, we investigate optimal coding theorems in the time-bounded setting. Our main contributions can be summarised as follows. • Efficient coding theorem for rKt with a factor of 2. Addressing a question from [Zhenjian Lu and Igor C. Oliveira, 2021], we show that if x can be efficiently sampled with probability at least δ then rKt(x) ≤ (2 + o(1)) ⋅ log(1/δ) + O(log n). As in previous work, our coding theorem is efficient in the sense that it provides a polynomial-time probabilistic algorithm that, when given x, the code of the sampler, and δ, it outputs, with probability ≥ 0.99, a probabilistic representation of x that certifies this rKt complexity bound. • Optimality under a cryptographic assumption. Under a hypothesis about the security of cryptographic pseudorandom generators, we show that no efficient coding theorem can achieve a bound of the form rKt(x) ≤ (2 - o(1)) ⋅ log(1/δ) + poly(log n). Under a weaker assumption, we exhibit a gap between efficient coding theorems and existential coding theorems with near-optimal parameters. • Optimal coding theorem for pK^t and unconditional Antunes-Fortnow. We consider pK^t complexity [Halley Goldberg et al., 2022], a variant of rKt where the randomness is public and the time bound is fixed. We observe the existence of an optimal coding theorem for pK^t, and employ this result to establish an unconditional version of a theorem of Antunes and Fortnow [Luis Filipe Coelho Antunes and Lance Fortnow, 2009] which characterizes the worst-case running times of languages that are in average polynomial-time over all 𝖯-samplable distributions.
Cite as

Zhenjian Lu, Igor C. Oliveira, and Marius Zimand. Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 92:1-92:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{lu_et_al:LIPIcs.ICALP.2022.92,
  author =	{Lu, Zhenjian and Oliveira, Igor C. and Zimand, Marius},
  title =	{{Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{92:1--92:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.92},
  URN =		{urn:nbn:de:0030-drops-164331},
  doi =		{10.4230/LIPIcs.ICALP.2022.92},
  annote =	{Keywords: computational complexity, randomized algorithms, Kolmogorov complexity}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.FSTTCS.2021.1
BQP After 28 Years (Invited Talk)

Authors: Scott Aaronson

Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)

Abstract
I will discuss the now-ancient question of where BQP, Bounded-Error Quantum Polynomial-Time, fits in among classical complexity classes. After reviewing some basics from the 90s, I will discuss the Forrelation problem that I introduced in 2009 to yield an oracle separation between BQP and PH, and the dramatic completion of that program by Ran Raz and Avishay Tal in 2018. I will then discuss very recent work, with William Kretschmer and DeVon Ingram, which leverages the Raz-Tal theorem, along with a new "quantum-aware" random restriction method, to obtain results that illustrate just how differently BQP can behave from BPP. These include oracles relative to which NP^{BQP} ̸ ⊂ BQP^{PH} - solving a 2005 open problem of Lance Fortnow - and conversely, relative to which BQP^{NP} ̸ ⊂ PH^{BQP}; an oracle relative to which 𝖯 = NP and yet BQP ≠ QCMA; an oracle relative to which NP ⊆ BQP yet PH is infinite; an oracle relative to which 𝖯 = NP≠ BQP = PP; and an oracle relative to which PP = PostBQP ̸ ⊂ QMA^{QMA^{…}}. By popular demand, I will also speculate about the status of BQP in the unrelativized world.
Cite as

Scott Aaronson. BQP After 28 Years (Invited Talk). In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, p. 1:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{aaronson:LIPIcs.FSTTCS.2021.1,
  author =	{Aaronson, Scott},
  title =	{{BQP After 28 Years}},
  booktitle =	{41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
  pages =	{1:1--1:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-215-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{213},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.1},
  URN =		{urn:nbn:de:0030-drops-155124},
  doi =		{10.4230/LIPIcs.FSTTCS.2021.1},
  annote =	{Keywords: quantum computing, complexity theory, oracle separations, circuit lower bounds}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2020.34
Approaching MCSP from Above and Below: Hardness for a Conditional Variant and AC^0[p]

Authors: Rahul Ilango

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract
The Minimum Circuit Size Problem (MCSP) asks whether a given Boolean function has a circuit of at most a given size. MCSP has been studied for over a half-century and has deep connections throughout theoretical computer science including to cryptography, computational learning theory, and proof complexity. For example, we know (informally) that if MCSP is easy to compute, then most cryptography can be broken. Despite this cryptographic hardness connection and extensive research, we still know relatively little about the hardness of MCSP unconditionally. Indeed, until very recently it was unknown whether MCSP can be computed in AC^0[2] (Golovnev et al., ICALP 2019). Our main contribution in this paper is to formulate a new "oracle" variant of circuit complexity and prove that this problem is NP-complete under randomized reductions. In more detail, we define the Minimum Oracle Circuit Size Problem (MOCSP) that takes as input the truth table of a Boolean function f, a size threshold s, and the truth table of an oracle Boolean function O, and determines whether there is a circuit with O-oracle gates and at most s wires that computes f. We prove that MOCSP is NP-complete under randomized polynomial-time reductions. We also extend the recent AC^0[p] lower bound against MCSP by Golovnev et al. to a lower bound against the circuit minimization problem for depth-d formulas, (AC^0_d)-MCSP. We view this result as primarily a technical contribution. In particular, our proof takes a radically different approach from prior MCSP-related hardness results.
Cite as

Rahul Ilango. Approaching MCSP from Above and Below: Hardness for a Conditional Variant and AC^0[p]. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 34:1-34:26, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{ilango:LIPIcs.ITCS.2020.34,
  author =	{Ilango, Rahul},
  title =	{{Approaching MCSP from Above and Below: Hardness for a Conditional Variant and AC^0\lbrackp\rbrack}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{34:1--34:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.34},
  URN =		{urn:nbn:de:0030-drops-117191},
  doi =		{10.4230/LIPIcs.ITCS.2020.34},
  annote =	{Keywords: Minimum Circuit Size Problem, reductions, NP-completeness, circuit lower bounds}
}
Document
DOI: 10.4230/LIPIcs.CCC.2016.19
New Non-Uniform Lower Bounds for Uniform Classes

Authors: Lance Fortnow and Rahul Santhanam

Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)

Abstract
We strengthen the nondeterministic hierarchy theorem for non-deterministic polynomial time to show that the lower bound holds against sub-linear advice. More formally, we show that for any constants d and d' such that 1 <= d < d', and for any time-constructible bound t=o(n^d), there is a language in NTIME(n^d) which is not in NTIME(t)/n^{1/d'}. The best known earlier separation of Fortnow, Santhanam and Trevisan could only handle o(log(n)) bits of advice in the lower bound, and was not tight with respect to the time bounds. We generalize our hierarchy theorem to work for other syntactic complexity measures between polynomial time and polynomial space, including alternating polynomial time with any fixed number of alternations. We also use our technique to derive an almost-everywhere hierarchy theorem for non-deterministic classes which use a sub-linear amount of non-determinism, i.e., the lower bound holds on all but finitely many input lengths rather than just on infinitely many. As one application of our main result, we derive a new lower bound for NP against NP-uniform non-deterministic circuits of size O(n^k) for any fixed k. This result is a significant strengthening of a result of Kannan, which states that not all of NP can be solved with P-uniform circuits of size O(n^k) for any fixed k. As another application, we show strong non-uniform lower bounds for the complexity class RE of languages decidable in randomized linear exponential time with one sided error.
Cite as

Lance Fortnow and Rahul Santhanam. New Non-Uniform Lower Bounds for Uniform Classes. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 19:1-19:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{fortnow_et_al:LIPIcs.CCC.2016.19,
  author =	{Fortnow, Lance and Santhanam, Rahul},
  title =	{{New Non-Uniform Lower Bounds for Uniform Classes}},
  booktitle =	{31st Conference on Computational Complexity (CCC 2016)},
  pages =	{19:1--19:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-008-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{50},
  editor =	{Raz, Ran},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.19},
  URN =		{urn:nbn:de:0030-drops-58503},
  doi =		{10.4230/LIPIcs.CCC.2016.19},
  annote =	{Keywords: Computational complexity, nondeterminism, nonuniform complexity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2010.2471
Inseparability and Strong Hypotheses for Disjoint NP Pairs

Authors: Lance Fortnow, Jack H. Lutz, and Elvira Mayordomo

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract
This paper investigates the existence of inseparable disjoint pairs of NP languages and related strong hypotheses in computational complexity. Our main theorem says that, if NP does not have measure 0 in EXP, then there exist disjoint pairs of NP languages that are P-inseparable, in fact TIME(2(n k))-inseparable. We also relate these conditions to strong hypotheses concerning randomness and genericity of disjoint pairs.
Cite as

Lance Fortnow, Jack H. Lutz, and Elvira Mayordomo. Inseparability and Strong Hypotheses for Disjoint NP Pairs. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 395-404, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{fortnow_et_al:LIPIcs.STACS.2010.2471,
  author =	{Fortnow, Lance and Lutz, Jack H. and Mayordomo, Elvira},
  title =	{{Inseparability and Strong Hypotheses for Disjoint NP Pairs}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{395--404},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2471},
  URN =		{urn:nbn:de:0030-drops-24711},
  doi =		{10.4230/LIPIcs.STACS.2010.2471},
  annote =	{Keywords: Computational Complexity, Disjoint NP-pairs, Resource-Bounded Measure, Genericity}
}
Document
DOI: 10.4230/DagSemProc.09421.1
09421 Abstracts Collection – Algebraic Methods in Computational Complexity

Authors: Manindra Agrawal, Lance Fortnow, Thomas Thierauf, and Christopher Umans

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

Abstract
From 11.10. to 16.10.2009, the Dagstuhl Seminar 09421 ``Algebraic Methods in Computational Complexity '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. 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, Lance Fortnow, Thomas Thierauf, and Christopher Umans. 09421 Abstracts Collection – Algebraic Methods in Computational Complexity. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 9421, pp. 1-22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:DagSemProc.09421.1,
  author =	{Agrawal, Manindra and Fortnow, Lance and Thierauf, Thomas and Umans, Christopher},
  title =	{{09421 Abstracts Collection – Algebraic Methods in Computational Complexity}},
  booktitle =	{Algebraic Methods in Computational Complexity},
  pages =	{1--22},
  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.1},
  URN =		{urn:nbn:de:0030-drops-24181},
  doi =		{10.4230/DagSemProc.09421.1},
  annote =	{Keywords: Computational Complexity, Algebra}
}
Document
DOI: 10.4230/DagSemProc.09421.2
09421 Executive Summary – Algebraic Methods in Computational Complexity

Authors: Manindra Agrawal, Lance Fortnow, Thomas Thierauf, and Christopher Umans

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

Abstract
The seminar brought together more than 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, most of them about 40 minutes leaving ample room for discussions. We also had a much appreciated open problem session. The talks ranged over a broad assortment of subjects with the underlying theme of using algebraic techniques. It was very fruitful and has hopefully initiated new directions in research. Several participants specifically mentioned that they appreciated the particular focus on a common class of techniques (rather than end results) as a unifying theme of the workshop. We look forward to our next meeting!
Cite as

Manindra Agrawal, Lance Fortnow, Thomas Thierauf, and Christopher Umans. 09421 Executive Summary – Algebraic Methods in Computational Complexity. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 9421, pp. 1-4, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:DagSemProc.09421.2,
  author =	{Agrawal, Manindra and Fortnow, Lance and Thierauf, Thomas and Umans, Christopher},
  title =	{{09421 Executive Summary – Algebraic Methods in Computational Complexity}},
  booktitle =	{Algebraic Methods in Computational Complexity},
  pages =	{1--4},
  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.2},
  URN =		{urn:nbn:de:0030-drops-24100},
  doi =		{10.4230/DagSemProc.09421.2},
  annote =	{Keywords: Computational Complexity, Algebra}
}
Document
DOI: 10.4230/DagSemProc.09421.3
An Axiomatic Approach to Algebrization

Authors: Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova

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

Abstract
Non-relativization of complexity issues can be interpreted as giving some evidence that these issues cannot be resolved by "black-box" techniques. In the early 1990's, a sequence of important non-relativizing results was proved, mainly using algebraic techniques. Two approaches have been proposed to understand the power and limitations of these algebraic techniques: (1) Fortnow gives a construction of a class of oracles which have a similar algebraic and logical structure, although they are arbitrarily powerful. He shows that many of the non-relativizing results proved using algebraic techniques hold for all such oracles, but he does not show, e.g., that the outcome of the "P vs. NP" question differs between different oracles in that class. (2) Aaronson and Wigderson give definitions of algebrizing separations and collapses of complexity classes, by comparing classes relative to one oracle to classes relative to an algebraic extension of that oracle. Using these definitions, they show both that the standard collapses and separations "algebrize" and that many of the open questions in complexity fail to "algebrize", suggesting that the arithmetization technique is close to its limits. However, it is unclear how to formalize algebrization of more complicated complexity statements than collapses or separations, and whether the algebrizing statements are, e.g., closed under modus ponens; so it is conceivable that several algebrizing premises could imply (in a relativizing way) a non-algebrizing conclusion. Here, building on the work of Arora, Impagliazzo, and Vazirani [4], we propose an axiomatic approach to "algebrization", which complements and clarifies the approaches of Fortnow and Aaronso&Wigderson. We present logical theories formalizing the notion of algebrizing techniques so that most algebrizing results are provable within our theories and separations requiring non-algebrizing techniques are independent of them. Our theories extend the [AIV] theory formalizing relativization by adding an Arithmetic Checkability axiom. We show the following: (i) Arithmetic checkability holds relative to arbitrarily powerful oracles (since Fortnow's algebraic oracles all satisfy Arithmetic Checkability axiom); by contrast, Local Checkability of [AIV] restricts the oracle power to NP cap co-NP. (ii) Most of the algebrizing collapses and separations from [AW], such as IP = PSPACE, NP subset ZKIP if one-way functions exist, MA-EXP not in P/poly, etc., are provable from Arithmetic Checkability. (iii) Many of the open complexity questions (shown to require nonalgebrizing techniques in [AW]), such as "P vs. NP", "NP vs. BPP", etc., cannot be proved from Arithmetic Checkability. (iv) Arithmetic Checkability is also insufficient to prove one known result, NEXP = MIP.
Cite as

Russell Impagliazzo, Valentine Kabanets, and Antonina Kolokolova. An Axiomatic Approach to Algebrization. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 9421, pp. 1-19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{impagliazzo_et_al:DagSemProc.09421.3,
  author =	{Impagliazzo, Russell and Kabanets, Valentine and Kolokolova, Antonina},
  title =	{{An Axiomatic Approach to Algebrization}},
  booktitle =	{Algebraic Methods in Computational Complexity},
  pages =	{1--19},
  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.3},
  URN =		{urn:nbn:de:0030-drops-24150},
  doi =		{10.4230/DagSemProc.09421.3},
  annote =	{Keywords: Oracles, arithmetization, algebrization}
}
Document
DOI: 10.4230/DagSemProc.09421.4
Deterministic approximation algorithms for the nearest codeword problem

Authors: Noga Alon, Rina Panigrahy, and Sergey Yekhanin

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

Abstract
The Nearest Codeword Problem (NCP) is a basic algorithmic question in the theory of error-correcting codes. Given a point v in F_2^n and a linear space L in F_2^n of dimension k NCP asks to find a point l in L that minimizes the (Hamming) distance from v. It is well-known that the nearest codeword problem is NP-hard. Therefore approximation algorithms are of interest. The best effcient approximation algorithms for the NCP to date are due to Berman and Karpinski. They are a deterministic algorithm that achieves an approximation ratio of O(k/c) for an arbitrary constant c; and a randomized algorithm that achieves an approximation ratio of O(k/ log n). In this paper we present new deterministic algorithms for approximating the NCP that improve substantially upon the earlier work, (almost) de-randomizing the randomized algorithm of Berman and Karpinski. We also initiate a study of the following Remote Point Problem (RPP). Given a linear space L in F_2^n of dimension k RPP asks to find a point v in F_2^n that is far from L. We say that an algorithm achieves a remoteness of r for the RPP if it always outputs a point v that is at least r-far from L. In this paper we present a deterministic polynomial time algorithm that achieves a remoteness of Omega(n log k / k) for all k < n/2. We motivate the remote point problem by relating it to both the nearest codeword problem and the matrix rigidity approach to circuit lower bounds in computational complexity theory.
Cite as

Noga Alon, Rina Panigrahy, and Sergey Yekhanin. Deterministic approximation algorithms for the nearest codeword problem. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 9421, pp. 1-13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{alon_et_al:DagSemProc.09421.4,
  author =	{Alon, Noga and Panigrahy, Rina and Yekhanin, Sergey},
  title =	{{Deterministic approximation algorithms for the nearest codeword problem}},
  booktitle =	{Algebraic Methods in Computational Complexity},
  pages =	{1--13},
  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.4},
  URN =		{urn:nbn:de:0030-drops-24133},
  doi =		{10.4230/DagSemProc.09421.4},
  annote =	{Keywords: }
}
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.6
Planar Graph Isomorphism is in Log-Space

Authors: Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, and Fabian Wagner

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

Abstract
Graph Isomorphism is the prime example of a computational problem with a wide difference between the best known lower and upper bounds on its complexity. There is a significant gap between extant lower and upper bounds for planar graphs as well. We bridge the gap for this natural and important special case by presenting an upper bound that matches the known log-space hardness [JKMT03]. In fact, we show the formally stronger result that planar graph canonization is in log-space. This improves the previously known upper bound of AC1 [MR91]. Our algorithm first constructs the biconnected component tree of a connected planar graph and then refines each biconnected component into a triconnected component tree. The next step is to log-space reduce the biconnected planar graph isomorphism and canonization problems to those for 3-connected planar graphs, which are known to be in log-space by [DLN08]. This is achieved by using the above decomposition, and by making significant modifications to Lindell’s algorithm for tree canonization, along with changes in the space complexity analysis. The reduction from the connected case to the biconnected case requires further new ideas including a non-trivial case analysis and a group theoretic lemma to bound the number of automorphisms of a colored 3-connected planar graph.
Cite as

Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, and Fabian Wagner. Planar Graph Isomorphism is in Log-Space. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 9421, pp. 1-32, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{datta_et_al:DagSemProc.09421.6,
  author =	{Datta, Samir and Limaye, Nutan and Nimbhorkar, Prajakta and Thierauf, Thomas and Wagner, Fabian},
  title =	{{Planar Graph Isomorphism is in Log-Space}},
  booktitle =	{Algebraic Methods in Computational Complexity},
  pages =	{1--32},
  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.6},
  URN =		{urn:nbn:de:0030-drops-24169},
  doi =		{10.4230/DagSemProc.09421.6},
  annote =	{Keywords: Planar Graphs, Graph Isomorphism, Logspace}
}
Document
DOI: 10.4230/DagSemProc.09421.7
Small space analogues of Valiant's classes and the limitations of skew formula

Authors: Meena Mahajan and Raghavendra Rao B. V.

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

Abstract
In the uniform circuit model of computation, the width of a boolean circuit exactly characterises the ``space'' complexity of the computed function. Looking for a similar relationship in Valiant's algebraic model of computation, we propose width of an arithmetic circuit as a possible measure of space. We introduce the class VL as an algebraic variant of deterministic log-space L. In the uniform setting, we show that our definition coincides with that of VPSPACE at polynomial width. Further, to define algebraic variants of non-deterministic space-bounded classes, we introduce the notion of ``read-once'' certificates for arithmetic circuits. We show that polynomial-size algebraic branching programs can be expressed as a read-once exponential sum over polynomials in VL, ie $mbox{VBP}inSigma^R cdotmbox{VL}$. We also show that $Sigma^R cdot mbox{VBP} =mbox{VBP}$, ie VBPs are stable under read-once exponential sums. Further, we show that read-once exponential sums over a restricted class of constant-width arithmetic circuits are within VQP, and this is the largest known such subclass of poly-log-width circuits with this property. We also study the power of skew formulas and show that exponential sums of a skew formula cannot represent the determinant polynomial.
Cite as

Meena Mahajan and Raghavendra Rao B. V.. Small space analogues of Valiant's classes and the limitations of skew formula. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 9421, pp. 1-23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{mahajan_et_al:DagSemProc.09421.7,
  author =	{Mahajan, Meena and Rao B. V., Raghavendra},
  title =	{{Small space analogues of Valiant's classes and the limitations of   skew formula}},
  booktitle =	{Algebraic Methods in Computational Complexity},
  pages =	{1--23},
  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.7},
  URN =		{urn:nbn:de:0030-drops-24126},
  doi =		{10.4230/DagSemProc.09421.7},
  annote =	{Keywords: Algebraic circuits, space bounds, circuit width, nondeterministic circuits, skew formulas}
}
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.3
Classical Simulation Complexity of Quantum Branching Programs

Authors: Farid Ablayev

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

Abstract
We present classical simulation techniques for measure once quantum branching programs. For bounded error syntactic quantum branching program of width $w$ that computes a function with error $delta$ we present a classical deterministic branching program of the same length and width at most $(1+2/(1-2delta))^{2w}$ that computes the same function. Second technique is a classical stochastic simulation technique for bounded error and unbounded error quantum branching programs. Our result is that it is possible stochastically-classically simulate quantum branching programs with the same length and almost the same width, but we lost bounded error acceptance property.
Cite as

Farid Ablayev. Classical Simulation Complexity of Quantum Branching Programs. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 7411, pp. 1-10, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{ablayev:DagSemProc.07411.3,
  author =	{Ablayev, Farid},
  title =	{{Classical Simulation Complexity of  Quantum  Branching Programs}},
  booktitle =	{Algebraic Methods in Computational Complexity},
  pages =	{1--10},
  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.3},
  URN =		{urn:nbn:de:0030-drops-13107},
  doi =		{10.4230/DagSemProc.07411.3},
  annote =	{Keywords: Quantum algorithms, Branching Programs, Complexity}
}
  • Refine by Author
  • 9 Fortnow, Lance
  • 7 Buhrman, Harry
  • 7 Thierauf, Thomas
  • 4 Agrawal, Manindra
  • 2 Aaronson, Scott
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Quantum complexity theory
  • 1 Theory of computation
  • 1 Theory of computation → Circuit complexity
  • 1 Theory of computation → Complexity classes
  • 1 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 4 Computational complexity
  • 3 Computational Complexity
  • 3 quantum computing
  • 2 (de-) randomization
  • 2 Algebra
  • Show More...

  • Refine by Type
  • 28 document

  • Refine by Publication Year
  • 9 2010
  • 7 2008
  • 6 2005
  • 2 2022
  • 1 2003
  • Show More...

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 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact