Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
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)
@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} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
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)
@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} }
Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)
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)
@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} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
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)
@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} }
Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)
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)
@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} }
Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)
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)
@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} }
Published in: Dagstuhl Seminar Proceedings, Volume 9421, Algebraic Methods in Computational Complexity (2010)
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)
@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} }
Published in: Dagstuhl Seminar Proceedings, Volume 9421, Algebraic Methods in Computational Complexity (2010)
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)
@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} }
Published in: Dagstuhl Seminar Proceedings, Volume 9421, Algebraic Methods in Computational Complexity (2010)
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)
@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} }
Published in: Dagstuhl Seminar Proceedings, Volume 9421, Algebraic Methods in Computational Complexity (2010)
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)
@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: } }
Published in: Dagstuhl Seminar Proceedings, Volume 9421, Algebraic Methods in Computational Complexity (2010)
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)
@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} }
Published in: Dagstuhl Seminar Proceedings, Volume 9421, Algebraic Methods in Computational Complexity (2010)
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)
@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} }
Published in: Dagstuhl Seminar Proceedings, Volume 9421, Algebraic Methods in Computational Complexity (2010)
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)
@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} }
Published in: Dagstuhl Seminar Proceedings, Volume 9421, Algebraic Methods in Computational Complexity (2010)
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)
@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} }
Published in: Dagstuhl Seminar Proceedings, Volume 7411, Algebraic Methods in Computational Complexity (2008)
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)
@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} }
Feedback for Dagstuhl Publishing