Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Lukáš Folwarczný, Mika Göös, Pavel Hubáček, Gilbert Maystre, and Weiqiang Yuan. One-Way Functions vs. TFNP: Simpler and Improved. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 50:1-50:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{folwarczny_et_al:LIPIcs.ITCS.2024.50, author = {Folwarczn\'{y}, Luk\'{a}\v{s} and G\"{o}\"{o}s, Mika and Hub\'{a}\v{c}ek, Pavel and Maystre, Gilbert and Yuan, Weiqiang}, title = {{One-Way Functions vs. TFNP: Simpler and Improved}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {50:1--50:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.50}, URN = {urn:nbn:de:0030-drops-195788}, doi = {10.4230/LIPIcs.ITCS.2024.50}, annote = {Keywords: TFNP, One-Way Functions, Oracle, Separation, Black-Box} }
Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Mika Göös, Ziyi Guan, and Tiberiu Mosnoi. Depth-3 Circuits for Inner Product. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 51:1-51:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{goos_et_al:LIPIcs.MFCS.2023.51, author = {G\"{o}\"{o}s, Mika and Guan, Ziyi and Mosnoi, Tiberiu}, title = {{Depth-3 Circuits for Inner Product}}, booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)}, pages = {51:1--51:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-292-1}, ISSN = {1868-8969}, year = {2023}, volume = {272}, editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.51}, URN = {urn:nbn:de:0030-drops-185856}, doi = {10.4230/LIPIcs.MFCS.2023.51}, annote = {Keywords: Circuit complexity, inner product} }
Published in: LIPIcs, Volume 257, 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)
Johanne Cohen, Laurence Pilard, Mikaël Rabie, and Jonas Sénizergues. Making Self-Stabilizing Algorithms for Any Locally Greedy Problem. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{cohen_et_al:LIPIcs.SAND.2023.11, author = {Cohen, Johanne and Pilard, Laurence and Rabie, Mika\"{e}l and S\'{e}nizergues, Jonas}, title = {{Making Self-Stabilizing Algorithms for Any Locally Greedy Problem}}, booktitle = {2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)}, pages = {11:1--11:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-275-4}, ISSN = {1868-8969}, year = {2023}, volume = {257}, editor = {Doty, David and Spirakis, Paul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2023.11}, URN = {urn:nbn:de:0030-drops-179475}, doi = {10.4230/LIPIcs.SAND.2023.11}, annote = {Keywords: Greedy Problem, Ruling Set, Distance-K Coloring, Self-Stabilizing Algorithm} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Mika Göös and Siddhartha Jain. Communication Complexity of Collision. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 19:1-19:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{goos_et_al:LIPIcs.APPROX/RANDOM.2022.19, author = {G\"{o}\"{o}s, Mika and Jain, Siddhartha}, title = {{Communication Complexity of Collision}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {19:1--19:9}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-249-5}, ISSN = {1868-8969}, year = {2022}, volume = {245}, editor = {Chakrabarti, Amit and Swamy, Chaitanya}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.19}, URN = {urn:nbn:de:0030-drops-171415}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.19}, annote = {Keywords: Collision, Communication complexity, Lifting} }
Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Antoine Amarilli and Mikaël Monet. Weighted Counting of Matchings in Unbounded-Treewidth Graph Families. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 9:1-9:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{amarilli_et_al:LIPIcs.MFCS.2022.9, author = {Amarilli, Antoine and Monet, Mika\"{e}l}, title = {{Weighted Counting of Matchings in Unbounded-Treewidth Graph Families}}, booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)}, pages = {9:1--9:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-256-3}, ISSN = {1868-8969}, year = {2022}, volume = {241}, editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.9}, URN = {urn:nbn:de:0030-drops-168078}, doi = {10.4230/LIPIcs.MFCS.2022.9}, annote = {Keywords: Treewidth, counting complexity, matchings, Fibonacci sequence} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, and Ran Tao. Further Collapses in TFNP. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 33:1-33:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{goos_et_al:LIPIcs.CCC.2022.33, author = {G\"{o}\"{o}s, Mika and Hollender, Alexandros and Jain, Siddhartha and Maystre, Gilbert and Pires, William and Robere, Robert and Tao, Ran}, title = {{Further Collapses in TFNP}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {33:1--33:15}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.33}, URN = {urn:nbn:de:0030-drops-165954}, doi = {10.4230/LIPIcs.CCC.2022.33}, annote = {Keywords: TFNP, PPAD, PLS, EOPL} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Mika Göös, Stefan Kiefer, and Weiqiang Yuan. Lower Bounds for Unambiguous Automata via Communication Complexity. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 126:1-126:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{goos_et_al:LIPIcs.ICALP.2022.126, author = {G\"{o}\"{o}s, Mika and Kiefer, Stefan and Yuan, Weiqiang}, title = {{Lower Bounds for Unambiguous Automata via Communication Complexity}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {126:1--126:13}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.126}, URN = {urn:nbn:de:0030-drops-164679}, doi = {10.4230/LIPIcs.ICALP.2022.126}, annote = {Keywords: Unambiguous automata, communication complexity} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Noah Fleming, Mika Göös, Stefan Grosser, and Robert Robere. On Semi-Algebraic Proofs and Algorithms. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 69:1-69:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{fleming_et_al:LIPIcs.ITCS.2022.69, author = {Fleming, Noah and G\"{o}\"{o}s, Mika and Grosser, Stefan and Robere, Robert}, title = {{On Semi-Algebraic Proofs and Algorithms}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {69:1--69:25}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.69}, URN = {urn:nbn:de:0030-drops-156658}, doi = {10.4230/LIPIcs.ITCS.2022.69}, annote = {Keywords: Proof Complexity, Extended Formulations, Circuit Complexity, Sherali-Adams} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, and Avi Wigderson. On the Power and Limitations of Branch and Cut. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 6:1-6:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{fleming_et_al:LIPIcs.CCC.2021.6, author = {Fleming, Noah and G\"{o}\"{o}s, Mika and Impagliazzo, Russell and Pitassi, Toniann and Robere, Robert and Tan, Li-Yang and Wigderson, Avi}, title = {{On the Power and Limitations of Branch and Cut}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {6:1--6:30}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-193-1}, ISSN = {1868-8969}, year = {2021}, volume = {200}, editor = {Kabanets, Valentine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.6}, URN = {urn:nbn:de:0030-drops-142809}, doi = {10.4230/LIPIcs.CCC.2021.6}, annote = {Keywords: Proof Complexity, Integer Programming, Cutting Planes, Branch and Cut, Stabbing Planes} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Mika Göös and Gilbert Maystre. A Majority Lemma for Randomised Query Complexity. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 18:1-18:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{goos_et_al:LIPIcs.CCC.2021.18, author = {G\"{o}\"{o}s, Mika and Maystre, Gilbert}, title = {{A Majority Lemma for Randomised Query Complexity}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {18:1--18:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-193-1}, ISSN = {1868-8969}, year = {2021}, volume = {200}, editor = {Kabanets, Valentine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.18}, URN = {urn:nbn:de:0030-drops-142922}, doi = {10.4230/LIPIcs.CCC.2021.18}, annote = {Keywords: Query Complexity, Composition, Majority} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Anurag Anshu, Shalev Ben-David, and Srijita Kundu. On Query-To-Communication Lifting for Adversary Bounds. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 30:1-30:39, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{anshu_et_al:LIPIcs.CCC.2021.30, author = {Anshu, Anurag and Ben-David, Shalev and Kundu, Srijita}, title = {{On Query-To-Communication Lifting for Adversary Bounds}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {30:1--30:39}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-193-1}, ISSN = {1868-8969}, year = {2021}, volume = {200}, editor = {Kabanets, Valentine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.30}, URN = {urn:nbn:de:0030-drops-143042}, doi = {10.4230/LIPIcs.CCC.2021.30}, annote = {Keywords: Quantum computing, query complexity, communication complexity, lifting theorems, adversary method} }
Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Shalev Ben-David, Mika Göös, Robin Kothari, and Thomas Watson. When Is Amplification Necessary for Composition in Randomized Query Complexity?. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 28:1-28:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{bendavid_et_al:LIPIcs.APPROX/RANDOM.2020.28, author = {Ben-David, Shalev and G\"{o}\"{o}s, Mika and Kothari, Robin and Watson, Thomas}, title = {{When Is Amplification Necessary for Composition in Randomized Query Complexity?}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)}, pages = {28:1--28:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-164-1}, ISSN = {1868-8969}, year = {2020}, volume = {176}, editor = {Byrka, Jaros{\l}aw and Meka, Raghu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.28}, URN = {urn:nbn:de:0030-drops-126316}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.28}, annote = {Keywords: Amplification, composition, query complexity} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Mika Göös, Pritish Kamath, Katerina Sotiraki, and Manolis Zampetakis. On the Complexity of Modulo-q Arguments and the Chevalley - Warning Theorem. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 19:1-19:42, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{goos_et_al:LIPIcs.CCC.2020.19, author = {G\"{o}\"{o}s, Mika and Kamath, Pritish and Sotiraki, Katerina and Zampetakis, Manolis}, title = {{On the Complexity of Modulo-q Arguments and the Chevalley - Warning Theorem}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {19:1--19:42}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-156-6}, ISSN = {1868-8969}, year = {2020}, volume = {169}, editor = {Saraf, Shubhangi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.19}, URN = {urn:nbn:de:0030-drops-125712}, doi = {10.4230/LIPIcs.CCC.2020.19}, annote = {Keywords: Total NP Search Problems, Modulo-q arguments, Chevalley - Warning Theorem} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Andrew Bassilakis, Andrew Drucker, Mika Göös, Lunjia Hu, Weiyun Ma, and Li-Yang Tan. The Power of Many Samples in Query Complexity. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 9:1-9:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{bassilakis_et_al:LIPIcs.ICALP.2020.9, author = {Bassilakis, Andrew and Drucker, Andrew and G\"{o}\"{o}s, Mika and Hu, Lunjia and Ma, Weiyun and Tan, Li-Yang}, title = {{The Power of Many Samples in Query Complexity}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {9:1--9:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.9}, URN = {urn:nbn:de:0030-drops-124163}, doi = {10.4230/LIPIcs.ICALP.2020.9}, annote = {Keywords: Query complexity, Composition theorems} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Mika Göös and Thomas Watson. A Lower Bound for Sampling Disjoint Sets. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 51:1-51:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{goos_et_al:LIPIcs.APPROX-RANDOM.2019.51, author = {G\"{o}\"{o}s, Mika and Watson, Thomas}, title = {{A Lower Bound for Sampling Disjoint Sets}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {51:1--51:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-125-2}, ISSN = {1868-8969}, year = {2019}, volume = {145}, editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.51}, URN = {urn:nbn:de:0030-drops-112666}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.51}, annote = {Keywords: Communication complexity, set disjointness, sampling} }
Feedback for Dagstuhl Publishing