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 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Gil Cohen, Dor Minzer, Shir Peleg, Aaron Potechin, and Amnon Ta-Shma. Expander Random Walks: The General Case and Limitations. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 43:1-43:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{cohen_et_al:LIPIcs.ICALP.2022.43, author = {Cohen, Gil and Minzer, Dor and Peleg, Shir and Potechin, Aaron and Ta-Shma, Amnon}, title = {{Expander Random Walks: The General Case and Limitations}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {43:1--43:18}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.43}, URN = {urn:nbn:de:0030-drops-163849}, doi = {10.4230/LIPIcs.ICALP.2022.43}, annote = {Keywords: Expander Graphs, Random Walks, Lower Bounds} }
Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)
Shir Peleg and Amir Shpilka. Robust Sylvester-Gallai Type Theorem for Quadratic Polynomials. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 43:1-43:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{peleg_et_al:LIPIcs.SoCG.2022.43, author = {Peleg, Shir and Shpilka, Amir}, title = {{Robust Sylvester-Gallai Type Theorem for Quadratic Polynomials}}, booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)}, pages = {43:1--43:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-227-3}, ISSN = {1868-8969}, year = {2022}, volume = {224}, editor = {Goaoc, Xavier and Kerber, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.43}, URN = {urn:nbn:de:0030-drops-160515}, doi = {10.4230/LIPIcs.SoCG.2022.43}, annote = {Keywords: Sylvester-Gallai theorem, quadratic polynomials, Algebraic computation} }
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 189, 37th International Symposium on Computational Geometry (SoCG 2021)
Jacob Fox, János Pach, and Andrew Suk. Sunflowers in Set Systems of Bounded Dimension. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 37:1-37:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{fox_et_al:LIPIcs.SoCG.2021.37, author = {Fox, Jacob and Pach, J\'{a}nos and Suk, Andrew}, title = {{Sunflowers in Set Systems of Bounded Dimension}}, booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)}, pages = {37:1--37:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-184-9}, ISSN = {1868-8969}, year = {2021}, volume = {189}, editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.37}, URN = {urn:nbn:de:0030-drops-138366}, doi = {10.4230/LIPIcs.SoCG.2021.37}, annote = {Keywords: Sunflower, VC-dimension, Littlestone dimension, pseudodisks} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Shafi Goldwasser, Guy N. Rothblum, Jonathan Shafer, and Amir Yehudayoff. Interactive Proofs for Verifying Machine Learning. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 41:1-41:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{goldwasser_et_al:LIPIcs.ITCS.2021.41, author = {Goldwasser, Shafi and Rothblum, Guy N. and Shafer, Jonathan and Yehudayoff, Amir}, title = {{Interactive Proofs for Verifying Machine Learning}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {41:1--41:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-177-1}, ISSN = {1868-8969}, year = {2021}, volume = {185}, editor = {Lee, James R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.41}, URN = {urn:nbn:de:0030-drops-135806}, doi = {10.4230/LIPIcs.ITCS.2021.41}, annote = {Keywords: PAC learning, Fourier analysis of boolean functions, Complexity gaps, Complexity lower bounds, Goldreich-Levin algorithm, Kushilevitz-Mansour algorithm, Distribution testing} }
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} }
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 146, 33rd International Symposium on Distributed Computing (DISC 2019)
Pierluigi Crescenzi, Pierre Fraigniaud, and Ami Paz. Trade-Offs in Distributed Interactive Proofs. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{crescenzi_et_al:LIPIcs.DISC.2019.13, author = {Crescenzi, Pierluigi and Fraigniaud, Pierre and Paz, Ami}, title = {{Trade-Offs in Distributed Interactive Proofs}}, booktitle = {33rd International Symposium on Distributed Computing (DISC 2019)}, pages = {13:1--13:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-126-9}, ISSN = {1868-8969}, year = {2019}, volume = {146}, editor = {Suomela, Jukka}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.13}, URN = {urn:nbn:de:0030-drops-113202}, doi = {10.4230/LIPIcs.DISC.2019.13}, annote = {Keywords: Distributed interactive proofs, Distributed verification} }
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 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Mrinal Kumar, Rafael Oliveira, and Ramprasad Saptharishi. Towards Optimal Depth Reductions for Syntactically Multilinear Circuits. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 78:1-78:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{kumar_et_al:LIPIcs.ICALP.2019.78, author = {Kumar, Mrinal and Oliveira, Rafael and Saptharishi, Ramprasad}, title = {{Towards Optimal Depth Reductions for Syntactically Multilinear Circuits}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {78:1--78:15}, 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.78}, URN = {urn:nbn:de:0030-drops-106548}, doi = {10.4230/LIPIcs.ICALP.2019.78}, annote = {Keywords: arithmetic circuits, multilinear circuits, depth reduction, lower bounds} }
Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)
Shay Moran and Amir Yehudayoff. On Weak epsilon-Nets and the Radon Number. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 51:1-51:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{moran_et_al:LIPIcs.SoCG.2019.51, author = {Moran, Shay and Yehudayoff, Amir}, title = {{On Weak epsilon-Nets and the Radon Number}}, booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)}, pages = {51:1--51:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-104-7}, ISSN = {1868-8969}, year = {2019}, volume = {129}, editor = {Barequet, Gill and Wang, Yusu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.51}, URN = {urn:nbn:de:0030-drops-104551}, doi = {10.4230/LIPIcs.SoCG.2019.51}, annote = {Keywords: abstract convexity, weak epsilon nets, Radon number, VC dimension, Haussler packing lemma, Kneser graphs} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Iftach Haitner, Noam Mazor, Rotem Oshman, Omer Reingold, and Amir Yehudayoff. On the Communication Complexity of Key-Agreement Protocols. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 40:1-40:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{haitner_et_al:LIPIcs.ITCS.2019.40, author = {Haitner, Iftach and Mazor, Noam and Oshman, Rotem and Reingold, Omer and Yehudayoff, Amir}, title = {{On the Communication Complexity of Key-Agreement Protocols}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {40:1--40:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-095-8}, ISSN = {1868-8969}, year = {2019}, volume = {124}, editor = {Blum, Avrim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.40}, URN = {urn:nbn:de:0030-drops-101335}, doi = {10.4230/LIPIcs.ITCS.2019.40}, annote = {Keywords: key agreement, random oracle, communication complexity, Merkle's puzzles} }
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} }
Feedback for Dagstuhl Publishing