Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Slobodan Mitrović, Ronitt Rubinfeld, and Mihir Singhal. Locally Computing Edge Orientations. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 89:1-89:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{mitrovic_et_al:LIPIcs.ESA.2024.89, author = {Mitrovi\'{c}, Slobodan and Rubinfeld, Ronitt and Singhal, Mihir}, title = {{Locally Computing Edge Orientations}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {89:1--89:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-338-6}, ISSN = {1868-8969}, year = {2024}, volume = {308}, editor = {Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.89}, URN = {urn:nbn:de:0030-drops-211603}, doi = {10.4230/LIPIcs.ESA.2024.89}, annote = {Keywords: local computation algorithms, edge orientation, tree coloring} }
Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Alexander Golovnev, Zeyu Guo, Pooya Hatami, Satyajeet Nagargoje, and Chao Yan. Hilbert Functions and Low-Degree Randomness Extractors. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 41:1-41:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{golovnev_et_al:LIPIcs.APPROX/RANDOM.2024.41, author = {Golovnev, Alexander and Guo, Zeyu and Hatami, Pooya and Nagargoje, Satyajeet and Yan, Chao}, title = {{Hilbert Functions and Low-Degree Randomness Extractors}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {41:1--41:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-348-5}, ISSN = {1868-8969}, year = {2024}, volume = {317}, editor = {Kumar, Amit and Ron-Zewi, Noga}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.41}, URN = {urn:nbn:de:0030-drops-210345}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.41}, annote = {Keywords: Extractors, Dispersers, Circuits, Hilbert Function, Randomness, Low Degree Polynomials} }
Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Dean Doron, Jonathan Mosheiff, and Mary Wootters. When Do Low-Rate Concatenated Codes Approach The Gilbert-Varshamov Bound?. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 53:1-53:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{doron_et_al:LIPIcs.APPROX/RANDOM.2024.53, author = {Doron, Dean and Mosheiff, Jonathan and Wootters, Mary}, title = {{When Do Low-Rate Concatenated Codes Approach The Gilbert-Varshamov Bound?}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {53:1--53:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-348-5}, ISSN = {1868-8969}, year = {2024}, volume = {317}, editor = {Kumar, Amit and Ron-Zewi, Noga}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.53}, URN = {urn:nbn:de:0030-drops-210467}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.53}, annote = {Keywords: Error-correcting codes, Concatenated codes, Derandomization, Gilbert-Varshamov bound} }
Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Amey Bhangale, Mark Braverman, Subhash Khot, Yang P. Liu, and Dor Minzer. Parallel Repetition of k-Player Projection Games. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 54:1-54:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bhangale_et_al:LIPIcs.APPROX/RANDOM.2024.54, author = {Bhangale, Amey and Braverman, Mark and Khot, Subhash and Liu, Yang P. and Minzer, Dor}, title = {{Parallel Repetition of k-Player Projection Games}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {54:1--54:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-348-5}, ISSN = {1868-8969}, year = {2024}, volume = {317}, editor = {Kumar, Amit and Ron-Zewi, Noga}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.54}, URN = {urn:nbn:de:0030-drops-210475}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.54}, annote = {Keywords: Parallel Repetition, Multiplayer games, Projection games} }
Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Kuan Cheng, Minghui Ouyang, Chong Shangguan, and Yuanting Shen. When Can an Expander Code Correct Ω(n) Errors in O(n) Time?. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 61:1-61:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{cheng_et_al:LIPIcs.APPROX/RANDOM.2024.61, author = {Cheng, Kuan and Ouyang, Minghui and Shangguan, Chong and Shen, Yuanting}, title = {{When Can an Expander Code Correct \Omega(n) Errors in O(n) Time?}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {61:1--61:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-348-5}, ISSN = {1868-8969}, year = {2024}, volume = {317}, editor = {Kumar, Amit and Ron-Zewi, Noga}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.61}, URN = {urn:nbn:de:0030-drops-210543}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.61}, annote = {Keywords: expander codes, expander graphs, linear-time decoding} }
Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Kuan Cheng and Ruiyang Wu. Randomness Extractors in AC⁰ and NC¹: Optimal up to Constant Factors. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 69:1-69:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{cheng_et_al:LIPIcs.APPROX/RANDOM.2024.69, author = {Cheng, Kuan and Wu, Ruiyang}, title = {{Randomness Extractors in AC⁰ and NC¹: Optimal up to Constant Factors}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {69:1--69:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-348-5}, ISSN = {1868-8969}, year = {2024}, volume = {317}, editor = {Kumar, Amit and Ron-Zewi, Noga}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.69}, URN = {urn:nbn:de:0030-drops-210623}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.69}, annote = {Keywords: randomness extractor, uniform AC⁰, error reduction, uniform NC¹, disperser} }
Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Pranjal Dutta, Amit Sinhababu, and Thomas Thierauf. Derandomizing Multivariate Polynomial Factoring for Low Degree Factors. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 75:1-75:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{dutta_et_al:LIPIcs.APPROX/RANDOM.2024.75, author = {Dutta, Pranjal and Sinhababu, Amit and Thierauf, Thomas}, title = {{Derandomizing Multivariate Polynomial Factoring for Low Degree Factors}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {75:1--75:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-348-5}, ISSN = {1868-8969}, year = {2024}, volume = {317}, editor = {Kumar, Amit and Ron-Zewi, Noga}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.75}, URN = {urn:nbn:de:0030-drops-210687}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.75}, annote = {Keywords: algebraic complexity, factoring, low degree, weight isolation, divisibility} }
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
William M. Hoza. A Technique for Hardness Amplification Against AC⁰. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 1:1-1:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{hoza:LIPIcs.CCC.2024.1, author = {Hoza, William M.}, title = {{A Technique for Hardness Amplification Against AC⁰}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {1:1--1:20}, 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.1}, URN = {urn:nbn:de:0030-drops-203977}, doi = {10.4230/LIPIcs.CCC.2024.1}, annote = {Keywords: Bounded-depth circuits, average-case lower bounds, hardness amplification, XOR lemmas} }
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Joshua Cook and Dana Moshkovitz. Explicit Time and Space Efficient Encoders Exist Only with Random Access. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 5:1-5:54, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{cook_et_al:LIPIcs.CCC.2024.5, author = {Cook, Joshua and Moshkovitz, Dana}, title = {{Explicit Time and Space Efficient Encoders Exist Only with Random Access}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {5:1--5:54}, 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.5}, URN = {urn:nbn:de:0030-drops-204015}, doi = {10.4230/LIPIcs.CCC.2024.5}, annote = {Keywords: Time-Space Trade Offs, Error Correcting Codes, Encoders, Explicit Constructions, Streaming Lower Bounds, Sequential Access, Time-Space Lower Bounds, Lossless Condensers, Invertible Condensers, Condensers} }
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Gil Cohen and Tal Yankovitz. Asymptotically-Good RLCCs with (log n)^(2+o(1)) Queries. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{cohen_et_al:LIPIcs.CCC.2024.8, author = {Cohen, Gil and Yankovitz, Tal}, title = {{Asymptotically-Good RLCCs with (log n)^(2+o(1)) Queries}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {8:1--8:16}, 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.8}, URN = {urn:nbn:de:0030-drops-204045}, doi = {10.4230/LIPIcs.CCC.2024.8}, annote = {Keywords: Relaxed locally decodable codes, Relxaed locally correctable codes, RLCC, RLDC} }
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 300, 39th Computational Complexity Conference (CCC 2024)
Harm Derksen, Peter Ivanov, Chin Ho Lee, and Emanuele Viola. Pseudorandomness, Symmetry, Smoothing: I. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 18:1-18:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{derksen_et_al:LIPIcs.CCC.2024.18, author = {Derksen, Harm and Ivanov, Peter and Lee, Chin Ho and Viola, Emanuele}, title = {{Pseudorandomness, Symmetry, Smoothing: I}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {18:1--18:27}, 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.18}, URN = {urn:nbn:de:0030-drops-204144}, doi = {10.4230/LIPIcs.CCC.2024.18}, annote = {Keywords: pseudorandomness, k-wise uniform distributions, small-bias distributions, noise, symmetric tests, thresholds, Krawtchouk polynomials} }
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Kiran S. Kedlaya and Swastik Kopparty. On the Degree of Polynomials Computing Square Roots Mod p. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 25:1-25:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{kedlaya_et_al:LIPIcs.CCC.2024.25, author = {Kedlaya, Kiran S. and Kopparty, Swastik}, title = {{On the Degree of Polynomials Computing Square Roots Mod p}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {25:1--25: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.25}, URN = {urn:nbn:de:0030-drops-204219}, doi = {10.4230/LIPIcs.CCC.2024.25}, annote = {Keywords: Algebraic Computation, Polynomials, Computing Square roots, Reed-Solomon Codes} }
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Michael A. Forbes. Low-Depth Algebraic Circuit Lower Bounds over Any Field. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{forbes:LIPIcs.CCC.2024.31, author = {Forbes, Michael A.}, title = {{Low-Depth Algebraic Circuit Lower Bounds over Any Field}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {31:1--31:16}, 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.31}, URN = {urn:nbn:de:0030-drops-204271}, doi = {10.4230/LIPIcs.CCC.2024.31}, annote = {Keywords: algebraic circuits, lower bounds, low-depth circuits, positive characteristic} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Guy Goldberg. Linear Relaxed Locally Decodable and Correctable Codes Do Not Need Adaptivity and Two-Sided Error. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 74:1-74:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{goldberg:LIPIcs.ICALP.2024.74, author = {Goldberg, Guy}, title = {{Linear Relaxed Locally Decodable and Correctable Codes Do Not Need Adaptivity and Two-Sided Error}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {74:1--74: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.74}, URN = {urn:nbn:de:0030-drops-202174}, doi = {10.4230/LIPIcs.ICALP.2024.74}, annote = {Keywords: Locally decodable codes, Relaxed locally correctable codes, Relaxed locally decodable codes} }
Feedback for Dagstuhl Publishing