Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Joshua Cook and Dana Moshkovitz. Explicit Time and Space Efficient Encoders Exist Only with Random Access. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 5:1-5:54, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{cook_et_al:LIPIcs.CCC.2024.5, author = {Cook, Joshua and Moshkovitz, Dana}, title = {{Explicit Time and Space Efficient Encoders Exist Only with Random Access}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {5:1--5:54}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-331-7}, ISSN = {1868-8969}, year = {2024}, volume = {300}, editor = {Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.5}, URN = {urn:nbn:de:0030-drops-204015}, doi = {10.4230/LIPIcs.CCC.2024.5}, annote = {Keywords: Time-Space Trade Offs, Error Correcting Codes, Encoders, Explicit Constructions, Streaming Lower Bounds, Sequential Access, Time-Space Lower Bounds, Lossless Condensers, Invertible Condensers, Condensers} }
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Shuichi Hirahara, Valentine Kabanets, Zhenjian Lu, and Igor C. Oliveira. Exact Search-To-Decision Reductions for Time-Bounded Kolmogorov Complexity. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 29:1-29:56, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{hirahara_et_al:LIPIcs.CCC.2024.29, author = {Hirahara, Shuichi and Kabanets, Valentine and Lu, Zhenjian and Oliveira, Igor C.}, title = {{Exact Search-To-Decision Reductions for Time-Bounded Kolmogorov Complexity}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {29:1--29:56}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-331-7}, ISSN = {1868-8969}, year = {2024}, volume = {300}, editor = {Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.29}, URN = {urn:nbn:de:0030-drops-204256}, doi = {10.4230/LIPIcs.CCC.2024.29}, annote = {Keywords: average-case complexity, Kolmogorov complexity, search-to-decision reductions} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Kasper Green Larsen, Rasmus Pagh, Giuseppe Persiano, Toniann Pitassi, Kevin Yeo, and Or Zamir. Optimal Non-Adaptive Cell Probe Dictionaries and Hashing. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 104:1-104:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{larsen_et_al:LIPIcs.ICALP.2024.104, author = {Larsen, Kasper Green and Pagh, Rasmus and Persiano, Giuseppe and Pitassi, Toniann and Yeo, Kevin and Zamir, Or}, title = {{Optimal Non-Adaptive Cell Probe Dictionaries and Hashing}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {104:1--104:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.104}, URN = {urn:nbn:de:0030-drops-202471}, doi = {10.4230/LIPIcs.ICALP.2024.104}, annote = {Keywords: non-adaptive, cell probe, dictionary, hashing} }
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} }