Published in: LIPIcs, Volume 311, 35th International Conference on Concurrency Theory (CONCUR 2024)
Sougata Bose, Rasmus Ibsen-Jensen, David Purser, Patrick Totzke, and Pierre Vandenhove. The Power of Counting Steps in Quantitative Games. In 35th International Conference on Concurrency Theory (CONCUR 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 311, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bose_et_al:LIPIcs.CONCUR.2024.13, author = {Bose, Sougata and Ibsen-Jensen, Rasmus and Purser, David and Totzke, Patrick and Vandenhove, Pierre}, title = {{The Power of Counting Steps in Quantitative Games}}, booktitle = {35th International Conference on Concurrency Theory (CONCUR 2024)}, pages = {13:1--13:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-339-3}, ISSN = {1868-8969}, year = {2024}, volume = {311}, editor = {Majumdar, Rupak and Silva, Alexandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2024.13}, URN = {urn:nbn:de:0030-drops-207852}, doi = {10.4230/LIPIcs.CONCUR.2024.13}, annote = {Keywords: Games on graphs, Markov strategies, quantitative objectives, infinite-state systems} }
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 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Brynmor Chapman and R. Ryan Williams. Smaller ACC0 Circuits for Symmetric Functions. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 38:1-38:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{chapman_et_al:LIPIcs.ITCS.2022.38, author = {Chapman, Brynmor and Williams, R. Ryan}, title = {{Smaller ACC0 Circuits for Symmetric Functions}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {38:1--38:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-217-4}, ISSN = {1868-8969}, year = {2022}, volume = {215}, editor = {Braverman, Mark}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.38}, URN = {urn:nbn:de:0030-drops-156342}, doi = {10.4230/LIPIcs.ITCS.2022.38}, annote = {Keywords: ACC, CC, circuit complexity, symmetric functions, Chinese Remainder Theorem} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Eleni Batziou, Kristoffer Arnsfelt Hansen, and Kasper Høgh. Strong Approximate Consensus Halving and the Borsuk-Ulam Theorem. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 24:1-24:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{batziou_et_al:LIPIcs.ICALP.2021.24, author = {Batziou, Eleni and Hansen, Kristoffer Arnsfelt and H{\o}gh, Kasper}, title = {{Strong Approximate Consensus Halving and the Borsuk-Ulam Theorem}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {24:1--24:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.24}, URN = {urn:nbn:de:0030-drops-140939}, doi = {10.4230/LIPIcs.ICALP.2021.24}, annote = {Keywords: Consensus halving, Computational Complexity, Borsuk-Ulam} }
Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Kristoffer Arnsfelt Hansen and Steffan Christ Sølvsten. ∃ℝ-Completeness of Stationary Nash Equilibria in Perfect Information Stochastic Games. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 45:1-45:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{hansen_et_al:LIPIcs.MFCS.2020.45, author = {Hansen, Kristoffer Arnsfelt and S{\o}lvsten, Steffan Christ}, title = {{\exists\mathbb{R}-Completeness of Stationary Nash Equilibria in Perfect Information Stochastic Games}}, booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)}, pages = {45:1--45:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-159-7}, ISSN = {1868-8969}, year = {2020}, volume = {170}, editor = {Esparza, Javier and Kr\'{a}l', Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.45}, URN = {urn:nbn:de:0030-drops-127113}, doi = {10.4230/LIPIcs.MFCS.2020.45}, annote = {Keywords: Existential Theory of the Reals, Stationary Nash Equilibrium, Perfect Information Stochastic Games} }
Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Chen Dan, Kristoffer Arnsfelt Hansen, He Jiang, Liwei Wang, and Yuchen Zhou. Low Rank Approximation of Binary Matrices: Column Subset Selection and Generalizations. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 41:1-41:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{dan_et_al:LIPIcs.MFCS.2018.41, author = {Dan, Chen and Hansen, Kristoffer Arnsfelt and Jiang, He and Wang, Liwei and Zhou, Yuchen}, title = {{Low Rank Approximation of Binary Matrices: Column Subset Selection and Generalizations}}, booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)}, pages = {41:1--41:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-086-6}, ISSN = {1868-8969}, year = {2018}, volume = {117}, editor = {Potapov, Igor and Spirakis, Paul and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.41}, URN = {urn:nbn:de:0030-drops-96239}, doi = {10.4230/LIPIcs.MFCS.2018.41}, annote = {Keywords: Approximation Algorithms, Low Rank Approximation, Binary Matrices} }
Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Krishnendu Chatterjee, Kristoffer Arnsfelt Hansen, and Rasmus Ibsen-Jensen. Strategy Complexity of Concurrent Safety Games. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 55:1-55:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{chatterjee_et_al:LIPIcs.MFCS.2017.55, author = {Chatterjee, Krishnendu and Hansen, Kristoffer Arnsfelt and Ibsen-Jensen, Rasmus}, title = {{Strategy Complexity of Concurrent Safety Games}}, booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)}, pages = {55:1--55:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-046-0}, ISSN = {1868-8969}, year = {2017}, volume = {83}, editor = {Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.55}, URN = {urn:nbn:de:0030-drops-81203}, doi = {10.4230/LIPIcs.MFCS.2017.55}, annote = {Keywords: Concurrent games, Reachability and safety, Patience of strategies} }
Published in: Dagstuhl Seminar Proceedings, Volume 8381, Computational Complexity of Discrete Problems (2008)
Kristoffer Arnsfelt Hansen. Depth Reduction for Circuits with a Single Layer of Modular Counting Gates. In Computational Complexity of Discrete Problems. Dagstuhl Seminar Proceedings, Volume 8381, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
@InProceedings{hansen:DagSemProc.08381.4, author = {Hansen, Kristoffer Arnsfelt}, title = {{Depth Reduction for Circuits with a Single Layer of Modular Counting Gates}}, booktitle = {Computational Complexity of Discrete Problems}, pages = {1--11}, 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.4}, URN = {urn:nbn:de:0030-drops-17824}, doi = {10.4230/DagSemProc.08381.4}, annote = {Keywords: Boolean Circuits, Randomized Polynomials, Fourier sums} }
Feedback for Dagstuhl Publishing