Published in: Dagstuhl Reports, Volume 8, Issue 9 (2019)
Markus Bläser, Valentine Kabanets, Jacobo Torán, and Christopher Umans. Algebraic Methods in Computational Complexity (Dagstuhl Seminar 18391). In Dagstuhl Reports, Volume 8, Issue 9, pp. 133-153, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@Article{blaser_et_al:DagRep.8.9.133, author = {Bl\"{a}ser, Markus and Kabanets, Valentine and Tor\'{a}n, Jacobo and Umans, Christopher}, title = {{Algebraic Methods in Computational Complexity (Dagstuhl Seminar 18391)}}, pages = {133--153}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2019}, volume = {8}, number = {9}, editor = {Bl\"{a}ser, Markus and Kabanets, Valentine and Tor\'{a}n, Jacobo and Umans, Christopher}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.8.9.133}, URN = {urn:nbn:de:0030-drops-103438}, doi = {10.4230/DagRep.8.9.133}, annote = {Keywords: computational complexity, algebra, (de-) randomization, circuits, coding, lower bounds} }
Published in: Dagstuhl Reports, Volume 6, Issue 10 (2017)
Valentine Kabanets, Thomas Thierauf, Jacobo Tóran, and Christopher Umans. Algebraic Methods in Computational Complexity (Dagstuhl Seminar 16411). In Dagstuhl Reports, Volume 6, Issue 10, pp. 13-32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@Article{kabanets_et_al:DagRep.6.10.13, author = {Kabanets, Valentine and Thierauf, Thomas and T\'{o}ran, Jacobo and Umans, Christopher}, title = {{Algebraic Methods in Computational Complexity (Dagstuhl Seminar 16411)}}, pages = {13--32}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2017}, volume = {6}, number = {10}, editor = {Kabanets, Valentine and Thierauf, Thomas and T\'{o}ran, Jacobo and Umans, Christopher}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.6.10.13}, URN = {urn:nbn:de:0030-drops-69504}, doi = {10.4230/DagRep.6.10.13}, annote = {Keywords: Computational Complexity, lower bounds, approximation, pseudo-randomness, derandomization, circuits} }
Published in: LIPIcs, Volume 61, 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016)
Bill Fefferman and Christopher Umans. On the Power of Quantum Fourier Sampling. In 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 61, pp. 1:1-1:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{fefferman_et_al:LIPIcs.TQC.2016.1, author = {Fefferman, Bill and Umans, Christopher}, title = {{On the Power of Quantum Fourier Sampling}}, booktitle = {11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016)}, pages = {1:1--1:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-019-4}, ISSN = {1868-8969}, year = {2016}, volume = {61}, editor = {Broadbent, Anne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2016.1}, URN = {urn:nbn:de:0030-drops-66829}, doi = {10.4230/LIPIcs.TQC.2016.1}, annote = {Keywords: Quantum Complexity Theory, Sampling Complexity} }
Published in: Dagstuhl Reports, Volume 4, Issue 9 (2015)
Manindra Agrawal, Valentine Kabanets, Thomas Thierauf, and Christopher Umans. Algebra in Computational Complexity (Dagstuhl Seminar 14391). In Dagstuhl Reports, Volume 4, Issue 9, pp. 85-105, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@Article{agrawal_et_al:DagRep.4.9.85, author = {Agrawal, Manindra and Kabanets, Valentine and Thierauf, Thomas and Umans, Christopher}, title = {{Algebra in Computational Complexity (Dagstuhl Seminar 14391)}}, pages = {85--105}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2015}, volume = {4}, number = {9}, editor = {Agrawal, Manindra and Kabanets, Valentine and Thierauf, Thomas and Umans, Christopher}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.4.9.85}, URN = {urn:nbn:de:0030-drops-48851}, doi = {10.4230/DagRep.4.9.85}, annote = {Keywords: Computational Complexity, lower bounds, approximazation, pseudo-randomness, derandomization, circuits} }
Published in: Dagstuhl Reports, Volume 2, Issue 10 (2013)
Manindra Agrawal, Thomas Thierauf, and Christopher Umans. Algebraic and Combinatorial Methods in Computational Complexity (Dagstuhl Seminar 12421). In Dagstuhl Reports, Volume 2, Issue 10, pp. 60-78, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@Article{agrawal_et_al:DagRep.2.10.60, author = {Agrawal, Manindra and Thierauf, Thomas and Umans, Christopher}, title = {{Algebraic and Combinatorial Methods in Computational Complexity (Dagstuhl Seminar 12421)}}, pages = {60--78}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2013}, volume = {2}, number = {10}, editor = {Agrawal, Manindra and Thierauf, Thomas and Umans, Christopher}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.2.10.60}, URN = {urn:nbn:de:0030-drops-39034}, doi = {10.4230/DagRep.2.10.60}, annote = {Keywords: Computational Complexity, lower bounds, approximazation, pseudo-randomness, derandomization, circuits} }
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 8381, Computational Complexity of Discrete Problems (2008)
Kiran Kedlaya and Christopher Umans. Fast polynomial factorization and modular composition. In Computational Complexity of Discrete Problems. Dagstuhl Seminar Proceedings, Volume 8381, pp. 1-33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
@InProceedings{kedlaya_et_al:DagSemProc.08381.5, author = {Kedlaya, Kiran and Umans, Christopher}, title = {{Fast polynomial factorization and modular composition}}, booktitle = {Computational Complexity of Discrete Problems}, pages = {1--33}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2008}, volume = {8381}, editor = {Peter Bro Miltersen and R\"{u}diger Reischuk and Georg Schnitger and Dieter van Melkebeek}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08381.5}, URN = {urn:nbn:de:0030-drops-17771}, doi = {10.4230/DagSemProc.08381.5}, annote = {Keywords: Modular composition; polynomial factorization; multipoint evaluation; Chinese Remaindering} }
Feedback for Dagstuhl Publishing