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-dev.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-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 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-dev.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-dev.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-dev.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-dev.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} }
Feedback for Dagstuhl Publishing