Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
Artur Ignatiev, Ivan Mihajlin, and Alexander Smal. Super-Cubic Lower Bound for Generalized Karchmer-Wigderson Games. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 66:1-66:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{ignatiev_et_al:LIPIcs.ISAAC.2022.66, author = {Ignatiev, Artur and Mihajlin, Ivan and Smal, Alexander}, title = {{Super-Cubic Lower Bound for Generalized Karchmer-Wigderson Games}}, booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)}, pages = {66:1--66:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-258-7}, ISSN = {1868-8969}, year = {2022}, volume = {248}, editor = {Bae, Sang Won and Park, Heejin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.66}, URN = {urn:nbn:de:0030-drops-173510}, doi = {10.4230/LIPIcs.ISAAC.2022.66}, annote = {Keywords: communication complexity, circuit complexity, Karchmer-Wigderson games} }
Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Gregory Emdin, Alexander S. Kulikov, Ivan Mihajlin, and Nikita Slezkin. CNF Encodings of Parity. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 47:1-47:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{emdin_et_al:LIPIcs.MFCS.2022.47, author = {Emdin, Gregory and Kulikov, Alexander S. and Mihajlin, Ivan and Slezkin, Nikita}, title = {{CNF Encodings of Parity}}, booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)}, pages = {47:1--47:12}, 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.47}, URN = {urn:nbn:de:0030-drops-168455}, doi = {10.4230/LIPIcs.MFCS.2022.47}, annote = {Keywords: encoding, parity, lower bounds, circuits, CNF} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Ivan Mihajlin and Anastasia Sofronova. A Better-Than-3log(n) Depth Lower Bound for De Morgan Formulas with Restrictions on Top Gates. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 13:1-13:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{mihajlin_et_al:LIPIcs.CCC.2022.13, author = {Mihajlin, Ivan and Sofronova, Anastasia}, title = {{A Better-Than-3log(n) Depth Lower Bound for De Morgan Formulas with Restrictions on Top Gates}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {13:1--13: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.13}, URN = {urn:nbn:de:0030-drops-165755}, doi = {10.4230/LIPIcs.CCC.2022.13}, annote = {Keywords: formula complexity, communication complexity, Karchmer-Raz-Wigderson conjecture, De Morgan formulas} }
Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Marek Cygan, Alexander S. Kulikov, Ivan Mihajlin, Maksim Nikolaev, and Grigory Reznikov. Minimum Common String Partition: Exact Algorithms. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 35:1-35:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{cygan_et_al:LIPIcs.ESA.2021.35, author = {Cygan, Marek and Kulikov, Alexander S. and Mihajlin, Ivan and Nikolaev, Maksim and Reznikov, Grigory}, title = {{Minimum Common String Partition: Exact Algorithms}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {35:1--35:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-204-4}, ISSN = {1868-8969}, year = {2021}, volume = {204}, editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.35}, URN = {urn:nbn:de:0030-drops-146167}, doi = {10.4230/LIPIcs.ESA.2021.35}, annote = {Keywords: similarity measure, string distance, exact algorithms, upper bounds, lower bounds} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Ivan Mihajlin and Alexander Smal. Toward Better Depth Lower Bounds: The XOR-KRW Conjecture. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 38:1-38:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{mihajlin_et_al:LIPIcs.CCC.2021.38, author = {Mihajlin, Ivan and Smal, Alexander}, title = {{Toward Better Depth Lower Bounds: The XOR-KRW Conjecture}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {38:1--38:24}, 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.38}, URN = {urn:nbn:de:0030-drops-143121}, doi = {10.4230/LIPIcs.CCC.2021.38}, annote = {Keywords: communication complexity, KRW conjecture, circuit complexity, half-duplex communication complexity, Karchmer-Wigderson games, multiplexer relation, universal relation} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Fedor V. Fomin, Daniel Lokshtanov, Ivan Mihajlin, Saket Saurabh, and Meirav Zehavi. Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 49:1-49:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{fomin_et_al:LIPIcs.ICALP.2020.49, author = {Fomin, Fedor V. and Lokshtanov, Daniel and Mihajlin, Ivan and Saurabh, Saket and Zehavi, Meirav}, title = {{Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {49:1--49: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.49}, URN = {urn:nbn:de:0030-drops-124568}, doi = {10.4230/LIPIcs.ICALP.2020.49}, annote = {Keywords: Hadwiger Number, Exponential-Time Hypothesis, Exact Algorithms, Edge Contraction Problems} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Alexander Golovnev, Alexander S. Kulikov, Alexander Logunov, Ivan Mihajlin, and Maksim Nikolaev. Collapsing Superstring Conjecture. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 26:1-26:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{golovnev_et_al:LIPIcs.APPROX-RANDOM.2019.26, author = {Golovnev, Alexander and Kulikov, Alexander S. and Logunov, Alexander and Mihajlin, Ivan and Nikolaev, Maksim}, title = {{Collapsing Superstring Conjecture}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {26:1--26:23}, 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.26}, URN = {urn:nbn:de:0030-drops-112411}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.26}, annote = {Keywords: superstring, shortest common superstring, approximation, greedy algorithms, greedy conjecture} }
Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Kenneth Hoover, Russell Impagliazzo, Ivan Mihajlin, and Alexander V. Smal. Half-Duplex Communication Complexity. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 10:1-10:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{hoover_et_al:LIPIcs.ISAAC.2018.10, author = {Hoover, Kenneth and Impagliazzo, Russell and Mihajlin, Ivan and Smal, Alexander V.}, title = {{Half-Duplex Communication Complexity}}, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}, pages = {10:1--10:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-094-1}, ISSN = {1868-8969}, year = {2018}, volume = {123}, editor = {Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.10}, URN = {urn:nbn:de:0030-drops-99583}, doi = {10.4230/LIPIcs.ISAAC.2018.10}, annote = {Keywords: communication complexity, half-duplex channel, information theory} }
Published in: LIPIcs, Volume 102, 33rd Computational Complexity Conference (CCC 2018)
Marco L. Carmosino, Russell Impagliazzo, Shachar Lovett, and Ivan Mihajlin. Hardness Amplification for Non-Commutative Arithmetic Circuits. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{carmosino_et_al:LIPIcs.CCC.2018.12, author = {Carmosino, Marco L. and Impagliazzo, Russell and Lovett, Shachar and Mihajlin, Ivan}, title = {{Hardness Amplification for Non-Commutative Arithmetic Circuits}}, booktitle = {33rd Computational Complexity Conference (CCC 2018)}, pages = {12:1--12:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-069-9}, ISSN = {1868-8969}, year = {2018}, volume = {102}, editor = {Servedio, Rocco A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2018.12}, URN = {urn:nbn:de:0030-drops-88772}, doi = {10.4230/LIPIcs.CCC.2018.12}, annote = {Keywords: arithmetic circuits, hardness amplification, circuit lower bounds, non-commutative computation} }
Feedback for Dagstuhl Publishing