Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Prerona Chatterjee and Pavel Hrubeš. New Lower Bounds Against Homogeneous Non-Commutative Circuits. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 13:1-13:10, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{chatterjee_et_al:LIPIcs.CCC.2023.13, author = {Chatterjee, Prerona and Hrube\v{s}, Pavel}, title = {{New Lower Bounds Against Homogeneous Non-Commutative Circuits}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {13:1--13:10}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-282-2}, ISSN = {1868-8969}, year = {2023}, volume = {264}, editor = {Ta-Shma, Amnon}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.13}, URN = {urn:nbn:de:0030-drops-182835}, doi = {10.4230/LIPIcs.CCC.2023.13}, annote = {Keywords: Algebraic circuit complexity, Non-Commutative Circuits, Homogeneous Computation, Lower bounds against algebraic circuits} }
Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)
Arkadev Chattopadhyay, Utsab Ghosal, and Partha Mukhopadhyay. Robustly Separating the Arithmetic Monotone Hierarchy via Graph Inner-Product. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 12:1-12:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{chattopadhyay_et_al:LIPIcs.FSTTCS.2022.12, author = {Chattopadhyay, Arkadev and Ghosal, Utsab and Mukhopadhyay, Partha}, title = {{Robustly Separating the Arithmetic Monotone Hierarchy via Graph Inner-Product}}, booktitle = {42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)}, pages = {12:1--12:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-261-7}, ISSN = {1868-8969}, year = {2022}, volume = {250}, editor = {Dawar, Anuj and Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.12}, URN = {urn:nbn:de:0030-drops-174045}, doi = {10.4230/LIPIcs.FSTTCS.2022.12}, annote = {Keywords: Algebraic Complexity, Discrepancy, Lower Bounds, Monotone Computations} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Arkadev Chattopadhyay, Rajit Datta, Utsab Ghosal, and Partha Mukhopadhyay. Monotone Complexity of Spanning Tree Polynomial Re-Visited. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 39:1-39:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{chattopadhyay_et_al:LIPIcs.ITCS.2022.39, author = {Chattopadhyay, Arkadev and Datta, Rajit and Ghosal, Utsab and Mukhopadhyay, Partha}, title = {{Monotone Complexity of Spanning Tree Polynomial Re-Visited}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {39:1--39:21}, 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.39}, URN = {urn:nbn:de:0030-drops-156356}, doi = {10.4230/LIPIcs.ITCS.2022.39}, annote = {Keywords: Spanning Tree Polynomial, Monotone Computation, Lower Bounds, Communication Complexity} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Pavel Hrubeš and Amir Yehudayoff. Shadows of Newton Polytopes. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 9:1-9:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{hrubes_et_al:LIPIcs.CCC.2021.9, author = {Hrube\v{s}, Pavel and Yehudayoff, Amir}, title = {{Shadows of Newton Polytopes}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {9:1--9:23}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.9}, URN = {urn:nbn:de:0030-drops-142833}, doi = {10.4230/LIPIcs.CCC.2021.9}, annote = {Keywords: Newton polytope, Monotone arithmetic circuit} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Sivaramakrishnan Natarajan Ramamoorthy and Cyrus Rashtchian. Equivalence of Systematic Linear Data Structures and Matrix Rigidity. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 35:1-35:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{natarajanramamoorthy_et_al:LIPIcs.ITCS.2020.35, author = {Natarajan Ramamoorthy, Sivaramakrishnan and Rashtchian, Cyrus}, title = {{Equivalence of Systematic Linear Data Structures and Matrix Rigidity}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {35:1--35:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-134-4}, ISSN = {1868-8969}, year = {2020}, volume = {151}, editor = {Vidick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.35}, URN = {urn:nbn:de:0030-drops-117204}, doi = {10.4230/LIPIcs.ITCS.2020.35}, annote = {Keywords: matrix rigidity, systematic linear data structures, cell probe model, communication complexity} }
Published in: LIPIcs, Volume 152, 28th EACSL Annual Conference on Computer Science Logic (CSL 2020)
Iddo Tzameret. From Classical Proof Theory to P versus NP: a Guide to Bounded Theories (Invited Talk). In 28th EACSL Annual Conference on Computer Science Logic (CSL 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 152, pp. 5:1-5:2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{tzameret:LIPIcs.CSL.2020.5, author = {Tzameret, Iddo}, title = {{From Classical Proof Theory to P versus NP: a Guide to Bounded Theories}}, booktitle = {28th EACSL Annual Conference on Computer Science Logic (CSL 2020)}, pages = {5:1--5:2}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-132-0}, ISSN = {1868-8969}, year = {2020}, volume = {152}, editor = {Fern\'{a}ndez, Maribel and Muscholl, Anca}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2020.5}, URN = {urn:nbn:de:0030-drops-116482}, doi = {10.4230/LIPIcs.CSL.2020.5}, annote = {Keywords: Bounded arithmetic, complexity class separations, circuit complexity, proof complexity, weak theories of arithmetic, feasible mathematics} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
V. Arvind, Abhranil Chatterjee, Rajit Datta, and Partha Mukhopadhyay. Efficient Black-Box Identity Testing for Free Group Algebras. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 57:1-57:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{arvind_et_al:LIPIcs.APPROX-RANDOM.2019.57, author = {Arvind, V. and Chatterjee, Abhranil and Datta, Rajit and Mukhopadhyay, Partha}, title = {{Efficient Black-Box Identity Testing for Free Group Algebras}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {57:1--57:16}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.57}, URN = {urn:nbn:de:0030-drops-112723}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.57}, annote = {Keywords: Rational identity testing, Free group algebra, Noncommutative computation, Randomized algorithms} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Igor Carboni Oliveira, Ján Pich, and Rahul Santhanam. Hardness Magnification near State-Of-The-Art Lower Bounds. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 27:1-27:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{oliveira_et_al:LIPIcs.CCC.2019.27, author = {Oliveira, Igor Carboni and Pich, J\'{a}n and Santhanam, Rahul}, title = {{Hardness Magnification near State-Of-The-Art Lower Bounds}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {27:1--27:29}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-116-0}, ISSN = {1868-8969}, year = {2019}, volume = {137}, editor = {Shpilka, Amir}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.27}, URN = {urn:nbn:de:0030-drops-108494}, doi = {10.4230/LIPIcs.CCC.2019.27}, annote = {Keywords: Circuit Complexity, Minimum Circuit Size Problem, Kolmogorov Complexity} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Stefan Dantchev, Nicola Galesi, and Barnaby Martin. Resolution and the Binary Encoding of Combinatorial Principles. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 6:1-6:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{dantchev_et_al:LIPIcs.CCC.2019.6, author = {Dantchev, Stefan and Galesi, Nicola and Martin, Barnaby}, title = {{Resolution and the Binary Encoding of Combinatorial Principles}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {6:1--6:25}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-116-0}, ISSN = {1868-8969}, year = {2019}, volume = {137}, editor = {Shpilka, Amir}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.6}, URN = {urn:nbn:de:0030-drops-108287}, doi = {10.4230/LIPIcs.CCC.2019.6}, annote = {Keywords: Proof complexity, k-DNF resolution, binary encodings, Clique and Pigeonhole principle} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Pavel Hrubeš, Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao, and Amir Yehudayoff. Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 72:1-72:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{hrubes_et_al:LIPIcs.ICALP.2019.72, author = {Hrube\v{s}, Pavel and Natarajan Ramamoorthy, Sivaramakrishnan and Rao, Anup and Yehudayoff, Amir}, title = {{Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {72:1--72:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.72}, URN = {urn:nbn:de:0030-drops-106487}, doi = {10.4230/LIPIcs.ICALP.2019.72}, annote = {Keywords: Balancing sets, depth-2 threshold circuits, polynomials, majority, weighted thresholds} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Pavel Hrubes and Amir Yehudayoff. On Isoperimetric Profiles and Computational Complexity. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 89:1-89:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{hrubes_et_al:LIPIcs.ICALP.2016.89, author = {Hrubes, Pavel and Yehudayoff, Amir}, title = {{On Isoperimetric Profiles and Computational Complexity}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {89:1--89:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-013-2}, ISSN = {1868-8969}, year = {2016}, volume = {55}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.89}, URN = {urn:nbn:de:0030-drops-61964}, doi = {10.4230/LIPIcs.ICALP.2016.89}, annote = {Keywords: Monotone computation, separations, communication complexity, isoperimetry} }
Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Alexander Golovnev, Edward A. Hirsch, Alexander Knop, and Alexander S. Kulikov. On the Limits of Gate Elimination. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 46:1-46:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{golovnev_et_al:LIPIcs.MFCS.2016.46, author = {Golovnev, Alexander and Hirsch, Edward A. and Knop, Alexander and Kulikov, Alexander S.}, title = {{On the Limits of Gate Elimination}}, booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)}, pages = {46:1--46:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-016-3}, ISSN = {1868-8969}, year = {2016}, volume = {58}, editor = {Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.46}, URN = {urn:nbn:de:0030-drops-64593}, doi = {10.4230/LIPIcs.MFCS.2016.46}, annote = {Keywords: circuit complexity, lower bounds, gate elimination} }
Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)
Yuval Filmus, Pavel Hrubeš, and Massimo Lauria. Semantic Versus Syntactic Cutting Planes. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 35:1-35:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{filmus_et_al:LIPIcs.STACS.2016.35, author = {Filmus, Yuval and Hrube\v{s}, Pavel and Lauria, Massimo}, title = {{Semantic Versus Syntactic Cutting Planes}}, booktitle = {33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)}, pages = {35:1--35:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-001-9}, ISSN = {1868-8969}, year = {2016}, volume = {47}, editor = {Ollinger, Nicolas and Vollmer, Heribert}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.35}, URN = {urn:nbn:de:0030-drops-57367}, doi = {10.4230/LIPIcs.STACS.2016.35}, annote = {Keywords: proof complexity, cutting planes, lower bounds} }
Published in: LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015)
Pavel Hrubes and Anup Rao. Circuits with Medium Fan-In. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 381-391, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{hrubes_et_al:LIPIcs.CCC.2015.381, author = {Hrubes, Pavel and Rao, Anup}, title = {{Circuits with Medium Fan-In}}, booktitle = {30th Conference on Computational Complexity (CCC 2015)}, pages = {381--391}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-81-1}, ISSN = {1868-8969}, year = {2015}, volume = {33}, editor = {Zuckerman, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.381}, URN = {urn:nbn:de:0030-drops-50528}, doi = {10.4230/LIPIcs.CCC.2015.381}, annote = {Keywords: Boolean circuit, Complexity, Communication Complexity} }
Feedback for Dagstuhl Publishing