Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Dan Karliner, Roie Salama, and Amnon Ta-Shma. The Plane Test Is a Local Tester for Multiplicity Codes. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 14:1-14:33, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{karliner_et_al:LIPIcs.CCC.2022.14, author = {Karliner, Dan and Salama, Roie and Ta-Shma, Amnon}, title = {{The Plane Test Is a Local Tester for Multiplicity Codes}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {14:1--14:33}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.14}, URN = {urn:nbn:de:0030-drops-165761}, doi = {10.4230/LIPIcs.CCC.2022.14}, annote = {Keywords: local testing, multiplicity codes, Reed Muller codes} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Iden Kalemaj, Sofya Raskhodnikova, and Nithin Varma. Sublinear-Time Computation in the Presence of Online Erasures. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 90:1-90:25, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{kalemaj_et_al:LIPIcs.ITCS.2022.90, author = {Kalemaj, Iden and Raskhodnikova, Sofya and Varma, Nithin}, title = {{Sublinear-Time Computation in the Presence of Online Erasures}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {90:1--90:25}, 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.90}, URN = {urn:nbn:de:0030-drops-156867}, doi = {10.4230/LIPIcs.ITCS.2022.90}, annote = {Keywords: Randomized algorithms, property testing, Fourier analysis, linear functions, quadratic functions, Lipschitz and monotone functions, sorted sequences} }
Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)
Suryajith Chillara. Functional Lower Bounds for Restricted Arithmetic Circuits of Depth Four. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 14:1-14:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{chillara:LIPIcs.FSTTCS.2021.14, author = {Chillara, Suryajith}, title = {{Functional Lower Bounds for Restricted Arithmetic Circuits of Depth Four}}, booktitle = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)}, pages = {14:1--14:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-215-0}, ISSN = {1868-8969}, year = {2021}, volume = {213}, editor = {Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.14}, URN = {urn:nbn:de:0030-drops-155251}, doi = {10.4230/LIPIcs.FSTTCS.2021.14}, annote = {Keywords: Functional Lower Bounds, Boolean Circuit Lower Bounds, Depth Four, Connections to Boolean Complexity, Iterated Matrix Multiplication} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Zeyu Guo. Variety Evasive Subspace Families. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 20:1-20:33, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{guo:LIPIcs.CCC.2021.20, author = {Guo, Zeyu}, title = {{Variety Evasive Subspace Families}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {20:1--20:33}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.20}, URN = {urn:nbn:de:0030-drops-142949}, doi = {10.4230/LIPIcs.CCC.2021.20}, annote = {Keywords: algebraic complexity, dimension reduction, Noether normalization, polynomial identity testing, pseudorandomness, varieties} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Noga Ron-Zewi, Ronen Shaltiel, and Nithin Varma. Query Complexity Lower Bounds for Local List-Decoding and Hard-Core Predicates (Even for Small Rate and Huge Lists). In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 33:1-33:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{ronzewi_et_al:LIPIcs.ITCS.2021.33, author = {Ron-Zewi, Noga and Shaltiel, Ronen and Varma, Nithin}, title = {{Query Complexity Lower Bounds for Local List-Decoding and Hard-Core Predicates (Even for Small Rate and Huge Lists)}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {33:1--33:18}, 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.33}, URN = {urn:nbn:de:0030-drops-135724}, doi = {10.4230/LIPIcs.ITCS.2021.33}, annote = {Keywords: Local list-decoding, Hard-core predicates, Black-box reduction, Hadamard code} }
Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Mary Wootters. List-Decodability of Structured Ensembles of Codes (Invited Talk). In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 3:1-3:5, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{wootters:LIPIcs.MFCS.2020.3, author = {Wootters, Mary}, title = {{List-Decodability of Structured Ensembles of Codes}}, booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)}, pages = {3:1--3:5}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-159-7}, ISSN = {1868-8969}, year = {2020}, volume = {170}, editor = {Esparza, Javier and Kr\'{a}l', Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.3}, URN = {urn:nbn:de:0030-drops-126742}, doi = {10.4230/LIPIcs.MFCS.2020.3}, annote = {Keywords: Error Correcting Codes, List-Decoding} }
Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Ben Lund and Aditya Potukuchi. On the List Recoverability of Randomly Punctured Codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 30:1-30:11, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{lund_et_al:LIPIcs.APPROX/RANDOM.2020.30, author = {Lund, Ben and Potukuchi, Aditya}, title = {{On the List Recoverability of Randomly Punctured Codes}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)}, pages = {30:1--30:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-164-1}, ISSN = {1868-8969}, year = {2020}, volume = {176}, editor = {Byrka, Jaros{\l}aw and Meka, Raghu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.30}, URN = {urn:nbn:de:0030-drops-126330}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.30}, annote = {Keywords: List recovery, randomly punctured codes, Reed-Solomon codes} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Swastik Kopparty, Nicolas Resch, Noga Ron-Zewi, Shubhangi Saraf, and Shashwat Silas. On List Recovery of High-Rate Tensor Codes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 68:1-68:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{kopparty_et_al:LIPIcs.APPROX-RANDOM.2019.68, author = {Kopparty, Swastik and Resch, Nicolas and Ron-Zewi, Noga and Saraf, Shubhangi and Silas, Shashwat}, title = {{On List Recovery of High-Rate Tensor Codes}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {68:1--68: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.68}, URN = {urn:nbn:de:0030-drops-112832}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.68}, annote = {Keywords: Coding theory, Tensor codes, List-decoding and recovery, Local codes} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Stefan Dantchev, Nicola Galesi, and Barnaby Martin. Resolution and the Binary Encoding of Combinatorial Principles. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 6:1-6:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{dantchev_et_al:LIPIcs.CCC.2019.6, author = {Dantchev, Stefan and Galesi, Nicola and Martin, Barnaby}, title = {{Resolution and the Binary Encoding of Combinatorial Principles}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {6:1--6:25}, 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.6}, URN = {urn:nbn:de:0030-drops-108287}, doi = {10.4230/LIPIcs.CCC.2019.6}, annote = {Keywords: Proof complexity, k-DNF resolution, binary encodings, Clique and Pigeonhole principle} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Nader H. Bshouty. Almost Optimal Distribution-Free Junta Testing. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 2:1-2:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bshouty:LIPIcs.CCC.2019.2, author = {Bshouty, Nader H.}, title = {{Almost Optimal Distribution-Free Junta Testing}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {2:1--2:13}, 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.2}, URN = {urn:nbn:de:0030-drops-108249}, doi = {10.4230/LIPIcs.CCC.2019.2}, annote = {Keywords: Distribution-free property testing, k-Junta} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Irit Dinur, Prahladh Harsha, Tali Kaufman, and Noga Ron-Zewi. From Local to Robust Testing via Agreement Testing. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 29:1-29:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{dinur_et_al:LIPIcs.ITCS.2019.29, author = {Dinur, Irit and Harsha, Prahladh and Kaufman, Tali and Ron-Zewi, Noga}, title = {{From Local to Robust Testing via Agreement Testing}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {29:1--29:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-095-8}, ISSN = {1868-8969}, year = {2019}, volume = {124}, editor = {Blum, Avrim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.29}, URN = {urn:nbn:de:0030-drops-101221}, doi = {10.4230/LIPIcs.ITCS.2019.29}, annote = {Keywords: Local testing, Robust testing, Agreement testing, Affine-invariant codes, Lifted codes} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Sofya Raskhodnikova, Noga Ron-Zewi, and Nithin Varma. Erasures vs. Errors in Local Decoding and Property Testing. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 63:1-63:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{raskhodnikova_et_al:LIPIcs.ITCS.2019.63, author = {Raskhodnikova, Sofya and Ron-Zewi, Noga and Varma, Nithin}, title = {{Erasures vs. Errors in Local Decoding and Property Testing}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {63:1--63:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-095-8}, ISSN = {1868-8969}, year = {2019}, volume = {124}, editor = {Blum, Avrim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.63}, URN = {urn:nbn:de:0030-drops-101568}, doi = {10.4230/LIPIcs.ITCS.2019.63}, annote = {Keywords: Error-correcting codes, probabilistically checkable proofs (PCPs) of proximity, Hadamard code, local list decoding, tolerant testing} }
Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
Ralph Christian Bottesch, Dmitry Gavinsky, and Hartmut Klauck. Correlation in Hard Distributions in Communication Complexity. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 544-572, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{bottesch_et_al:LIPIcs.APPROX-RANDOM.2015.544, author = {Bottesch, Ralph Christian and Gavinsky, Dmitry and Klauck, Hartmut}, title = {{Correlation in Hard Distributions in Communication Complexity}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)}, pages = {544--572}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-89-7}, ISSN = {1868-8969}, year = {2015}, volume = {40}, editor = {Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.544}, URN = {urn:nbn:de:0030-drops-53234}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2015.544}, annote = {Keywords: communication complexity; information theory} }
Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
Mark Bun and Thomas Steinke. Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 625-644, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{bun_et_al:LIPIcs.APPROX-RANDOM.2015.625, author = {Bun, Mark and Steinke, Thomas}, title = {{Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)}, pages = {625--644}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-89-7}, ISSN = {1868-8969}, year = {2015}, volume = {40}, editor = {Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.625}, URN = {urn:nbn:de:0030-drops-53274}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2015.625}, annote = {Keywords: Polynomial Approximations, Pseudorandomness, Concentration, Learning Theory, Halfspaces} }
Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)
Pranjal Awasthi, Moses Charikar, Ravishankar Krishnaswamy, and Ali Kemal Sinop. The Hardness of Approximation of Euclidean k-Means. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 754-767, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{awasthi_et_al:LIPIcs.SOCG.2015.754, author = {Awasthi, Pranjal and Charikar, Moses and Krishnaswamy, Ravishankar and Sinop, Ali Kemal}, title = {{The Hardness of Approximation of Euclidean k-Means}}, booktitle = {31st International Symposium on Computational Geometry (SoCG 2015)}, pages = {754--767}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-83-5}, ISSN = {1868-8969}, year = {2015}, volume = {34}, editor = {Arge, Lars and Pach, J\'{a}nos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.754}, URN = {urn:nbn:de:0030-drops-51178}, doi = {10.4230/LIPIcs.SOCG.2015.754}, annote = {Keywords: Euclidean k-means, Hardness of Approximation, Vertex Cover} }
Feedback for Dagstuhl Publishing