Published in: LIPIcs, Volume 302, 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)
James Allen Fill, Daniel Q. Naiman, and Ao Sun. Sharpened Localization of the Trailing Point of the Pareto Record Frontier. In 35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 302, pp. 28:1-28:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{fill_et_al:LIPIcs.AofA.2024.28, author = {Fill, James Allen and Naiman, Daniel Q. and Sun, Ao}, title = {{Sharpened Localization of the Trailing Point of the Pareto Record Frontier}}, booktitle = {35th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2024)}, pages = {28:1--28:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-329-4}, ISSN = {1868-8969}, year = {2024}, volume = {302}, editor = {Mailler, C\'{e}cile and Wild, Sebastian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2024.28}, URN = {urn:nbn:de:0030-drops-204631}, doi = {10.4230/LIPIcs.AofA.2024.28}, annote = {Keywords: Multivariate records, Pareto records, generators, interior generators, minima, maxima, record-setting region, frontier, current records, boundary-crossing probabilities, first moment method, second moment method, orthants} }
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Mitali Bafna and Dor Minzer. Solving Unique Games over Globally Hypercontractive Graphs. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bafna_et_al:LIPIcs.CCC.2024.3, author = {Bafna, Mitali and Minzer, Dor}, title = {{Solving Unique Games over Globally Hypercontractive Graphs}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {3:1--3:15}, 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.3}, URN = {urn:nbn:de:0030-drops-203996}, doi = {10.4230/LIPIcs.CCC.2024.3}, annote = {Keywords: unique games, approximation algorithms} }
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Xin Li and Yan Zhong. Explicit Directional Affine Extractors and Improved Hardness for Linear Branching Programs. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{li_et_al:LIPIcs.CCC.2024.10, author = {Li, Xin and Zhong, Yan}, title = {{Explicit Directional Affine Extractors and Improved Hardness for Linear Branching Programs}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {10:1--10:14}, 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.10}, URN = {urn:nbn:de:0030-drops-204060}, doi = {10.4230/LIPIcs.CCC.2024.10}, annote = {Keywords: Randomness Extractors, Affine, Read-once Linear Branching Programs, Low-degree polynomials, AC⁰ circuits} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Aaron Potechin and Aaron Zhang. Bounds on the Total Coefficient Size of Nullstellensatz Proofs of the Pigeonhole Principle. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 117:1-117:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{potechin_et_al:LIPIcs.ICALP.2024.117, author = {Potechin, Aaron and Zhang, Aaron}, title = {{Bounds on the Total Coefficient Size of Nullstellensatz Proofs of the Pigeonhole Principle}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {117:1--117: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.117}, URN = {urn:nbn:de:0030-drops-202604}, doi = {10.4230/LIPIcs.ICALP.2024.117}, annote = {Keywords: Proof complexity, Nullstellensatz, pigeonhole principle, coefficient size} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Louis Golowich and Tali Kaufman. NLTS Hamiltonians and Strongly-Explicit SoS Lower Bounds from Low-Rate Quantum LDPC Codes. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 54:1-54:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{golowich_et_al:LIPIcs.ITCS.2024.54, author = {Golowich, Louis and Kaufman, Tali}, title = {{NLTS Hamiltonians and Strongly-Explicit SoS Lower Bounds from Low-Rate Quantum LDPC Codes}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {54:1--54: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.54}, URN = {urn:nbn:de:0030-drops-195829}, doi = {10.4230/LIPIcs.ITCS.2024.54}, annote = {Keywords: NLTS Hamiltonian, Quantum PCP, Sum-of-squares lower bound, Quantum LDPC code} }
Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)
Wenkai Dai, Michael Dinitz, Klaus-Tycho Foerster, and Stefan Schmid. Brief Announcement: Minimizing Congestion in Hybrid Demand-Aware Network Topologies. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 42:1-42:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{dai_et_al:LIPIcs.DISC.2022.42, author = {Dai, Wenkai and Dinitz, Michael and Foerster, Klaus-Tycho and Schmid, Stefan}, title = {{Brief Announcement: Minimizing Congestion in Hybrid Demand-Aware Network Topologies}}, booktitle = {36th International Symposium on Distributed Computing (DISC 2022)}, pages = {42:1--42:3}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-255-6}, ISSN = {1868-8969}, year = {2022}, volume = {246}, editor = {Scheideler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.42}, URN = {urn:nbn:de:0030-drops-172330}, doi = {10.4230/LIPIcs.DISC.2022.42}, annote = {Keywords: Congestion, Reconfigurable Networks, Algorithms, Complexity} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Jason Gaitonde, Max Hopkins, Tali Kaufman, Shachar Lovett, and Ruizhe Zhang. Eigenstripping, Spectral Decay, and Edge-Expansion on Posets. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 16:1-16:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{gaitonde_et_al:LIPIcs.APPROX/RANDOM.2022.16, author = {Gaitonde, Jason and Hopkins, Max and Kaufman, Tali and Lovett, Shachar and Zhang, Ruizhe}, title = {{Eigenstripping, Spectral Decay, and Edge-Expansion on Posets}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {16:1--16:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-249-5}, ISSN = {1868-8969}, year = {2022}, volume = {245}, editor = {Chakrabarti, Amit and Swamy, Chaitanya}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.16}, URN = {urn:nbn:de:0030-drops-171381}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.16}, annote = {Keywords: High-dimensional expanders, posets, eposets} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Prabhanjan Ananth, Abhishek Jain, Zhengzhong Jin, and Giulio Malavolta. Pre-Constrained Encryption. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 4:1-4:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{ananth_et_al:LIPIcs.ITCS.2022.4, author = {Ananth, Prabhanjan and Jain, Abhishek and Jin, Zhengzhong and Malavolta, Giulio}, title = {{Pre-Constrained Encryption}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {4:1--4:20}, 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.4}, URN = {urn:nbn:de:0030-drops-156001}, doi = {10.4230/LIPIcs.ITCS.2022.4}, annote = {Keywords: Advanced encryption systems} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Eden Chlamtáč, Michael Dinitz, and Thomas Robinson. Approximating the Norms of Graph Spanners. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 11:1-11:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{chlamtac_et_al:LIPIcs.APPROX-RANDOM.2019.11, author = {Chlamt\'{a}\v{c}, Eden and Dinitz, Michael and Robinson, Thomas}, title = {{Approximating the Norms of Graph Spanners}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {11:1--11:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-125-2}, ISSN = {1868-8969}, year = {2019}, volume = {145}, editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.11}, URN = {urn:nbn:de:0030-drops-112261}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.11}, annote = {Keywords: Spanners, Approximations} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Ryan O'Donnell and Tselil Schramm. Sherali - Adams Strikes Back. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 8:1-8:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{odonnell_et_al:LIPIcs.CCC.2019.8, author = {O'Donnell, Ryan and Schramm, Tselil}, title = {{Sherali - Adams Strikes Back}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {8:1--8:30}, 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.8}, URN = {urn:nbn:de:0030-drops-108309}, doi = {10.4230/LIPIcs.CCC.2019.8}, annote = {Keywords: Linear programming, Sherali, Adams, max-cut, graph eigenvalues, Sum-of-Squares} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Eden Chlamtáč, Michael Dinitz, and Thomas Robinson. The Norms of Graph Spanners. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 40:1-40:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{chlamtac_et_al:LIPIcs.ICALP.2019.40, author = {Chlamt\'{a}\v{c}, Eden and Dinitz, Michael and Robinson, Thomas}, title = {{The Norms of Graph Spanners}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {40:1--40: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.40}, URN = {urn:nbn:de:0030-drops-106163}, doi = {10.4230/LIPIcs.ICALP.2019.40}, annote = {Keywords: spanners, approximations} }
Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)
Vijay Bhattiprolu, Venkatesan Guruswami, and Euiwoong Lee. Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 31:1-31:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{bhattiprolu_et_al:LIPIcs.APPROX-RANDOM.2017.31, author = {Bhattiprolu, Vijay and Guruswami, Venkatesan and Lee, Euiwoong}, title = {{Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)}, pages = {31:1--31:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-044-6}, ISSN = {1868-8969}, year = {2017}, volume = {81}, editor = {Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.31}, URN = {urn:nbn:de:0030-drops-75808}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2017.31}, annote = {Keywords: Sum-of-Squares, Optimization over Sphere, Random Polynomials} }