Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Lianna Hambardzumyan, Toniann Pitassi, Suhail Sherif, Morgan Shirley, and Adi Shraibman. An Improved Protocol for ExactlyN with More Than 3 Players. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 58:1-58:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{hambardzumyan_et_al:LIPIcs.ITCS.2024.58, author = {Hambardzumyan, Lianna and Pitassi, Toniann and Sherif, Suhail and Shirley, Morgan and Shraibman, Adi}, title = {{An Improved Protocol for ExactlyN with More Than 3 Players}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {58:1--58:23}, 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.58}, URN = {urn:nbn:de:0030-drops-195868}, doi = {10.4230/LIPIcs.ITCS.2024.58}, annote = {Keywords: Corner-free sets, number-on-forehead communication} }
Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Nicola Galesi, Joshua A. Grochow, Toniann Pitassi, and Adrian She. On the Algebraic Proof Complexity of Tensor Isomorphism. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 4:1-4:40, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{galesi_et_al:LIPIcs.CCC.2023.4, author = {Galesi, Nicola and Grochow, Joshua A. and Pitassi, Toniann and She, Adrian}, title = {{On the Algebraic Proof Complexity of Tensor Isomorphism}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {4:1--4:40}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.4}, URN = {urn:nbn:de:0030-drops-182748}, doi = {10.4230/LIPIcs.CCC.2023.4}, annote = {Keywords: Algebraic proof complexity, Tensor Isomorphism, Graph Isomorphism, Polynomial Calculus, Sum-of-Squares, reductions, lower bounds, proof complexity of linear algebra} }
Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Russell Impagliazzo, Sasank Mouli, and Toniann Pitassi. Lower Bounds for Polynomial Calculus with Extension Variables over Finite Fields. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 7:1-7:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{impagliazzo_et_al:LIPIcs.CCC.2023.7, author = {Impagliazzo, Russell and Mouli, Sasank and Pitassi, Toniann}, title = {{Lower Bounds for Polynomial Calculus with Extension Variables over Finite Fields}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {7:1--7:24}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.7}, URN = {urn:nbn:de:0030-drops-182774}, doi = {10.4230/LIPIcs.CCC.2023.7}, annote = {Keywords: Proof complexity, Algebraic proof systems, Polynomial Calculus, Extension variables, AC⁰\lbrackp\rbrack-Frege} }
Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Josh Alman and Jarosław Błasiok. Matrix Multiplication and Number on the Forehead Communication. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 16:1-16:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{alman_et_al:LIPIcs.CCC.2023.16, author = {Alman, Josh and B{\l}asiok, Jaros{\l}aw}, title = {{Matrix Multiplication and Number on the Forehead Communication}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {16:1--16:23}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.16}, URN = {urn:nbn:de:0030-drops-182861}, doi = {10.4230/LIPIcs.CCC.2023.16}, annote = {Keywords: Number on the forehead, communication complexity, matrix multiplication} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Toniann Pitassi, Morgan Shirley, and Adi Shraibman. The Strength of Equality Oracles in Communication. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 89:1-89:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{pitassi_et_al:LIPIcs.ITCS.2023.89, author = {Pitassi, Toniann and Shirley, Morgan and Shraibman, Adi}, title = {{The Strength of Equality Oracles in Communication}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {89:1--89:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.89}, URN = {urn:nbn:de:0030-drops-175927}, doi = {10.4230/LIPIcs.ITCS.2023.89}, annote = {Keywords: Factorization norm, blocky rank, Merlin-Arthur} }
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-dev.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 234, 37th Computational Complexity Conference (CCC 2022)
James Cook and Ian Mertz. Trading Time and Space in Catalytic Branching Programs. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 8:1-8:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{cook_et_al:LIPIcs.CCC.2022.8, author = {Cook, James and Mertz, Ian}, title = {{Trading Time and Space in Catalytic Branching Programs}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {8:1--8:21}, 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.8}, URN = {urn:nbn:de:0030-drops-165708}, doi = {10.4230/LIPIcs.CCC.2022.8}, annote = {Keywords: complexity theory, branching programs, amortized, space complexity, catalytic computation} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter, and Toniann Pitassi. Secret Sharing, Slice Formulas, and Monotone Real Circuits. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 8:1-8:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{applebaum_et_al:LIPIcs.ITCS.2022.8, author = {Applebaum, Benny and Beimel, Amos and Nir, Oded and Peter, Naty and Pitassi, Toniann}, title = {{Secret Sharing, Slice Formulas, and Monotone Real Circuits}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {8:1--8:23}, 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.8}, URN = {urn:nbn:de:0030-drops-156046}, doi = {10.4230/LIPIcs.ITCS.2022.8}, annote = {Keywords: Secret Sharing Schemes, Monotone Real Circuits} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Noah Fleming, Toniann Pitassi, and Robert Robere. Extremely Deep Proofs. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 70:1-70:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{fleming_et_al:LIPIcs.ITCS.2022.70, author = {Fleming, Noah and Pitassi, Toniann and Robere, Robert}, title = {{Extremely Deep Proofs}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {70:1--70:23}, 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.70}, URN = {urn:nbn:de:0030-drops-156665}, doi = {10.4230/LIPIcs.ITCS.2022.70}, annote = {Keywords: Proof Complexity, Tradeoffs, Resolution, Cutting Planes} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Shachar Lovett, Raghu Meka, Ian Mertz, Toniann Pitassi, and Jiapeng Zhang. Lifting with Sunflowers. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 104:1-104:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{lovett_et_al:LIPIcs.ITCS.2022.104, author = {Lovett, Shachar and Meka, Raghu and Mertz, Ian and Pitassi, Toniann and Zhang, Jiapeng}, title = {{Lifting with Sunflowers}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {104:1--104:24}, 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.104}, URN = {urn:nbn:de:0030-drops-157004}, doi = {10.4230/LIPIcs.ITCS.2022.104}, annote = {Keywords: Lifting theorems, communication complexity, combinatorics, sunflowers} }
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)
Shafi Goldwasser, Russell Impagliazzo, Toniann Pitassi, and Rahul Santhanam. On the Pseudo-Deterministic Query Complexity of NP Search Problems. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 36:1-36:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{goldwasser_et_al:LIPIcs.CCC.2021.36, author = {Goldwasser, Shafi and Impagliazzo, Russell and Pitassi, Toniann and Santhanam, Rahul}, title = {{On the Pseudo-Deterministic Query Complexity of NP Search Problems}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {36:1--36:22}, 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.36}, URN = {urn:nbn:de:0030-drops-143104}, doi = {10.4230/LIPIcs.CCC.2021.36}, annote = {Keywords: Pseudo-determinism, Query complexity, Proof complexity} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Toniann Pitassi. Algebraic Proof Systems (Invited Talk). In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, p. 5:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{pitassi:LIPIcs.ICALP.2021.5, author = {Pitassi, Toniann}, title = {{Algebraic Proof Systems}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {5:1--5:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.5}, URN = {urn:nbn:de:0030-drops-140747}, doi = {10.4230/LIPIcs.ICALP.2021.5}, annote = {Keywords: complexity theory, proof complexity, algebraic circuits} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Aaron Potechin. Sum of Squares Bounds for the Ordering Principle. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 38:1-38:37, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{potechin:LIPIcs.CCC.2020.38, author = {Potechin, Aaron}, title = {{Sum of Squares Bounds for the Ordering Principle}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {38:1--38:37}, 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.38}, URN = {urn:nbn:de:0030-drops-125900}, doi = {10.4230/LIPIcs.CCC.2020.38}, annote = {Keywords: sum of squares hierarchy, proof complexity, ordering principle} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Toniann Pitassi, Morgan Shirley, and Thomas Watson. Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 92:1-92:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{pitassi_et_al:LIPIcs.ICALP.2020.92, author = {Pitassi, Toniann and Shirley, Morgan and Watson, Thomas}, title = {{Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {92:1--92:19}, 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.92}, URN = {urn:nbn:de:0030-drops-124992}, doi = {10.4230/LIPIcs.ICALP.2020.92}, annote = {Keywords: Boolean hierarchies, lifting theorems, query complexity} }
Feedback for Dagstuhl Publishing