Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Prashanth Amireddy, Ankit Garg, Neeraj Kayal, Chandan Saha, and Bhargav Thankey. Low-Depth Arithmetic Circuit Lower Bounds: Bypassing Set-Multilinearization. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 12:1-12:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{amireddy_et_al:LIPIcs.ICALP.2023.12, author = {Amireddy, Prashanth and Garg, Ankit and Kayal, Neeraj and Saha, Chandan and Thankey, Bhargav}, title = {{Low-Depth Arithmetic Circuit Lower Bounds: Bypassing Set-Multilinearization}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {12:1--12:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.12}, URN = {urn:nbn:de:0030-drops-180642}, doi = {10.4230/LIPIcs.ICALP.2023.12}, annote = {Keywords: arithmetic circuits, low-depth circuits, lower bounds, shifted partials} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Vishwas Bhargava and Sumanta Ghosh. Improved Hitting Set for Orbit of ROABPs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 30:1-30:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{bhargava_et_al:LIPIcs.APPROX/RANDOM.2021.30, author = {Bhargava, Vishwas and Ghosh, Sumanta}, title = {{Improved Hitting Set for Orbit of ROABPs}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {30:1--30:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-207-5}, ISSN = {1868-8969}, year = {2021}, volume = {207}, editor = {Wootters, Mary and Sanit\`{a}, Laura}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.30}, URN = {urn:nbn:de:0030-drops-147231}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.30}, annote = {Keywords: Hitting Set, Low Cone Concentration, Orbits, PIT, ROABP} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Chandan Saha and Bhargav Thankey. Hitting Sets for Orbits of Circuit Classes and Polynomial Families. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 50:1-50:26, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{saha_et_al:LIPIcs.APPROX/RANDOM.2021.50, author = {Saha, Chandan and Thankey, Bhargav}, title = {{Hitting Sets for Orbits of Circuit Classes and Polynomial Families}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {50:1--50:26}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-207-5}, ISSN = {1868-8969}, year = {2021}, volume = {207}, editor = {Wootters, Mary and Sanit\`{a}, Laura}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.50}, URN = {urn:nbn:de:0030-drops-147433}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.50}, annote = {Keywords: Hitting Sets, Orbits, ROABPs, Rank Concentration} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Nikhil Gupta, Chandan Saha, and Bhargav Thankey. A Super-Quadratic Lower Bound for Depth Four Arithmetic Circuits. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 23:1-23:31, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{gupta_et_al:LIPIcs.CCC.2020.23, author = {Gupta, Nikhil and Saha, Chandan and Thankey, Bhargav}, title = {{A Super-Quadratic Lower Bound for Depth Four Arithmetic Circuits}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {23:1--23:31}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.23}, URN = {urn:nbn:de:0030-drops-125757}, doi = {10.4230/LIPIcs.CCC.2020.23}, annote = {Keywords: depth four arithmetic circuits, Projected Shifted Partials, super-quadratic lower bound} }
Feedback for Dagstuhl Publishing