Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Yaroslav Alekseev, Yuval Filmus, and Alexander Smal. Lifting Dichotomies. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 9:1-9:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{alekseev_et_al:LIPIcs.CCC.2024.9, author = {Alekseev, Yaroslav and Filmus, Yuval and Smal, Alexander}, title = {{Lifting Dichotomies}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {9:1--9:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-331-7}, ISSN = {1868-8969}, year = {2024}, volume = {300}, editor = {Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.9}, URN = {urn:nbn:de:0030-drops-204051}, doi = {10.4230/LIPIcs.CCC.2024.9}, annote = {Keywords: decision trees, log-rank conjecture, lifting, parity decision trees} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Noel Arteche, Erfan Khaniki, Ján Pich, and Rahul Santhanam. From Proof Complexity to Circuit Complexity via Interactive Protocols. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 12:1-12:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{arteche_et_al:LIPIcs.ICALP.2024.12, author = {Arteche, Noel and Khaniki, Erfan and Pich, J\'{a}n and Santhanam, Rahul}, title = {{From Proof Complexity to Circuit Complexity via Interactive Protocols}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {12:1--12:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.12}, URN = {urn:nbn:de:0030-drops-201557}, doi = {10.4230/LIPIcs.ICALP.2024.12}, annote = {Keywords: proof complexity, circuit complexity, interactive protocols} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Holger Dell, John Lapinskas, and Kitty Meeks. Nearly Optimal Independence Oracle Algorithms for Edge Estimation in Hypergraphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 54:1-54:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{dell_et_al:LIPIcs.ICALP.2024.54, author = {Dell, Holger and Lapinskas, John and Meeks, Kitty}, title = {{Nearly Optimal Independence Oracle Algorithms for Edge Estimation in Hypergraphs}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {54:1--54:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.54}, URN = {urn:nbn:de:0030-drops-201977}, doi = {10.4230/LIPIcs.ICALP.2024.54}, annote = {Keywords: Graph oracles, Fine-grained complexity, Approximate counting, Hypergraphs} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Shachar Lovett and Jiapeng Zhang. Fractional Certificates for Bounded Functions. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 84:1-84:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{lovett_et_al:LIPIcs.ITCS.2023.84, author = {Lovett, Shachar and Zhang, Jiapeng}, title = {{Fractional Certificates for Bounded Functions}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {84:1--84:13}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.84}, URN = {urn:nbn:de:0030-drops-175871}, doi = {10.4230/LIPIcs.ITCS.2023.84}, annote = {Keywords: Aaronson-Ambainis conjecture, fractional block sensitivity, Talagrand inequality} }
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.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 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Benjamin Rossman. Shrinkage of Decision Lists and DNF Formulas. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 70:1-70:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{rossman:LIPIcs.ITCS.2021.70, author = {Rossman, Benjamin}, title = {{Shrinkage of Decision Lists and DNF Formulas}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {70:1--70:14}, 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.70}, URN = {urn:nbn:de:0030-drops-136098}, doi = {10.4230/LIPIcs.ITCS.2021.70}, annote = {Keywords: shrinkage, decision lists, DNF formulas} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Shachar Lovett, Noam Solomon, and Jiapeng Zhang. From DNF Compression to Sunflower Theorems via Regularity. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{lovett_et_al:LIPIcs.CCC.2019.5, author = {Lovett, Shachar and Solomon, Noam and Zhang, Jiapeng}, title = {{From DNF Compression to Sunflower Theorems via Regularity}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {5:1--5:14}, 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.5}, URN = {urn:nbn:de:0030-drops-108277}, doi = {10.4230/LIPIcs.CCC.2019.5}, annote = {Keywords: DNF sparsification, sunflower conjecture, regular set systems} }
Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)
Xin Li, Shachar Lovett, and Jiapeng Zhang. Sunflowers and Quasi-Sunflowers from Randomness Extractors. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 51:1-51:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{li_et_al:LIPIcs.APPROX-RANDOM.2018.51, author = {Li, Xin and Lovett, Shachar and Zhang, Jiapeng}, title = {{Sunflowers and Quasi-Sunflowers from Randomness Extractors}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)}, pages = {51:1--51:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-085-9}, ISSN = {1868-8969}, year = {2018}, volume = {116}, editor = {Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.51}, URN = {urn:nbn:de:0030-drops-94555}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2018.51}, annote = {Keywords: Sunflower conjecture, Quasi-sunflowers, Randomness Extractors} }
Published in: LIPIcs, Volume 102, 33rd Computational Complexity Conference (CCC 2018)
Yi-Hsiu Chen, Mika Göös, Salil P. Vadhan, and Jiapeng Zhang. A Tight Lower Bound for Entropy Flattening. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 23:1-23:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{chen_et_al:LIPIcs.CCC.2018.23, author = {Chen, Yi-Hsiu and G\"{o}\"{o}s, Mika and Vadhan, Salil P. and Zhang, Jiapeng}, title = {{A Tight Lower Bound for Entropy Flattening}}, booktitle = {33rd Computational Complexity Conference (CCC 2018)}, pages = {23:1--23:28}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2018.23}, URN = {urn:nbn:de:0030-drops-88669}, doi = {10.4230/LIPIcs.CCC.2018.23}, annote = {Keywords: Entropy, One-way function} }