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)
Hugo Aaronson, Tom Gur, Ninad Rajgopal, and Ron D. Rothblum. Distribution-Free Proofs of Proximity. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 24:1-24:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{aaronson_et_al:LIPIcs.CCC.2024.24, author = {Aaronson, Hugo and Gur, Tom and Rajgopal, Ninad and Rothblum, Ron D.}, title = {{Distribution-Free Proofs of Proximity}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {24:1--24: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.24}, URN = {urn:nbn:de:0030-drops-204204}, doi = {10.4230/LIPIcs.CCC.2024.24}, annote = {Keywords: Property Testing, Interactive Proofs, Distribution-Free Property Testing} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Esther Galby, Sándor Kisfaludi-Bak, Dániel Marx, and Roohani Sharma. Subexponential Parameterized Directed Steiner Network Problems on Planar Graphs: A Complete Classification. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 67:1-67:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{galby_et_al:LIPIcs.ICALP.2024.67, author = {Galby, Esther and Kisfaludi-Bak, S\'{a}ndor and Marx, D\'{a}niel and Sharma, Roohani}, title = {{Subexponential Parameterized Directed Steiner Network Problems on Planar Graphs: A Complete Classification}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {67:1--67:19}, 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.67}, URN = {urn:nbn:de:0030-drops-202104}, doi = {10.4230/LIPIcs.ICALP.2024.67}, annote = {Keywords: Directed Steiner Network, Sub-exponential algorithm} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Shuangle Li, Bingkai Lin, and Yuwei Liu. Improved Lower Bounds for Approximating Parameterized Nearest Codeword and Related Problems Under ETH. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 107:1-107:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{li_et_al:LIPIcs.ICALP.2024.107, author = {Li, Shuangle and Lin, Bingkai and Liu, Yuwei}, title = {{Improved Lower Bounds for Approximating Parameterized Nearest Codeword and Related Problems Under ETH}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {107:1--107: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.107}, URN = {urn:nbn:de:0030-drops-202500}, doi = {10.4230/LIPIcs.ICALP.2024.107}, annote = {Keywords: Nearest Codeword Problem, Hardness of Approximations, Fine-grained Complexity, Parameterized Complexity, Minimum Distance Problem, Shortest Vector Problem} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Augusto Modanese and Yuichi Yoshida. Testing Spreading Behavior in Networks with Arbitrary Topologies. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 112:1-112:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{modanese_et_al:LIPIcs.ICALP.2024.112, author = {Modanese, Augusto and Yoshida, Yuichi}, title = {{Testing Spreading Behavior in Networks with Arbitrary Topologies}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {112:1--112: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.112}, URN = {urn:nbn:de:0030-drops-202554}, doi = {10.4230/LIPIcs.ICALP.2024.112}, annote = {Keywords: Property testing, bootstrap percolation, local phenomena, expander graphs} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Omri Ben-Eliezer, Esty Kelman, Uri Meir, and Sofya Raskhodnikova. Property Testing with Online Adversaries. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 11:1-11:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{beneliezer_et_al:LIPIcs.ITCS.2024.11, author = {Ben-Eliezer, Omri and Kelman, Esty and Meir, Uri and Raskhodnikova, Sofya}, title = {{Property Testing with Online Adversaries}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {11:1--11:25}, 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.11}, URN = {urn:nbn:de:0030-drops-195395}, doi = {10.4230/LIPIcs.ITCS.2024.11}, annote = {Keywords: Linearity testing, low-degree testing, Reed-Muller codes, testing properties of sequences, erasure-resilience, corruption-resilience} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Andrej Bogdanov and Baoxiang Wang. Learning and Testing Variable Partitions. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 37:1-37:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{bogdanov_et_al:LIPIcs.ITCS.2020.37, author = {Bogdanov, Andrej and Wang, Baoxiang}, title = {{Learning and Testing Variable Partitions}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {37:1--37:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-134-4}, ISSN = {1868-8969}, year = {2020}, volume = {151}, editor = {Vidick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.37}, URN = {urn:nbn:de:0030-drops-117221}, doi = {10.4230/LIPIcs.ITCS.2020.37}, annote = {Keywords: partitioning, agnostic learning, property testing, sublinear-time algorithms, hypergraph cut, reinforcement learning} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Arnab Bhattacharyya, L. Sunil Chandran, and Suprovat Ghoshal. Combinatorial Lower Bounds for 3-Query LDCs. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 85:1-85:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{bhattacharyya_et_al:LIPIcs.ITCS.2020.85, author = {Bhattacharyya, Arnab and Chandran, L. Sunil and Ghoshal, Suprovat}, title = {{Combinatorial Lower Bounds for 3-Query LDCs}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {85:1--85:8}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-134-4}, ISSN = {1868-8969}, year = {2020}, volume = {151}, editor = {Vidick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.85}, URN = {urn:nbn:de:0030-drops-117704}, doi = {10.4230/LIPIcs.ITCS.2020.85}, annote = {Keywords: Coding theory, Graph theory, Hypergraphs} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S., and Pasin Manurangsi. Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{bhattacharyya_et_al:LIPIcs.ICALP.2018.17, author = {Bhattacharyya, Arnab and Ghoshal, Suprovat and C. S., Karthik and Manurangsi, Pasin}, title = {{Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {17:1--17:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.17}, URN = {urn:nbn:de:0030-drops-90214}, doi = {10.4230/LIPIcs.ICALP.2018.17}, annote = {Keywords: Parameterized Complexity, Inapproximability, Even Set, Minimum Distance Problem, Shortest Vector Problem, Gap-ETH} }
Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)
Arnab Bhattacharyya, Sivakanth Gopi, and Avishay Tal. Lower Bounds for 2-Query LCCs over Large Alphabet. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 30:1-30:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{bhattacharyya_et_al:LIPIcs.APPROX-RANDOM.2017.30, author = {Bhattacharyya, Arnab and Gopi, Sivakanth and Tal, Avishay}, title = {{Lower Bounds for 2-Query LCCs over Large Alphabet}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)}, pages = {30:1--30: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.30}, URN = {urn:nbn:de:0030-drops-75792}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2017.30}, annote = {Keywords: Locally correctable code, Private information retrieval, Szemer\'{e}di regularity lemma} }
Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Arnab Bhattacharyya, Abhishek Bhowmick, and Chetan Gupta. On Higher-Order Fourier Analysis over Non-Prime Fields. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 23:1-23:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{bhattacharyya_et_al:LIPIcs.APPROX-RANDOM.2016.23, author = {Bhattacharyya, Arnab and Bhowmick, Abhishek and Gupta, Chetan}, title = {{On Higher-Order Fourier Analysis over Non-Prime Fields}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)}, pages = {23:1--23:29}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-018-7}, ISSN = {1868-8969}, year = {2016}, volume = {60}, editor = {Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.23}, URN = {urn:nbn:de:0030-drops-66463}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2016.23}, annote = {Keywords: finite fields, higher order fourier analysis, coding theory, property testing} }
Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)
Arnab Bhattacharyya, Ameet Gadekar, Suprovat Ghoshal, and Rishi Saket. On the Hardness of Learning Sparse Parities. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{bhattacharyya_et_al:LIPIcs.ESA.2016.11, author = {Bhattacharyya, Arnab and Gadekar, Ameet and Ghoshal, Suprovat and Saket, Rishi}, title = {{On the Hardness of Learning Sparse Parities}}, booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)}, pages = {11:1--11:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-015-6}, ISSN = {1868-8969}, year = {2016}, volume = {57}, editor = {Sankowski, Piotr and Zaroliagis, Christos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.11}, URN = {urn:nbn:de:0030-drops-63628}, doi = {10.4230/LIPIcs.ESA.2016.11}, annote = {Keywords: Fixed Parameter Tractable, Juntas, Minimum Distance of Code, Psuedorandom Generators} }
Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)
Arnab Bhattacharyya and Sivakanth Gopi. Lower Bounds for Constant Query Affine-Invariant LCCs and LTCs. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{bhattacharyya_et_al:LIPIcs.CCC.2016.12, author = {Bhattacharyya, Arnab and Gopi, Sivakanth}, title = {{Lower Bounds for Constant Query Affine-Invariant LCCs and LTCs}}, booktitle = {31st Conference on Computational Complexity (CCC 2016)}, pages = {12:1--12:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-008-8}, ISSN = {1868-8969}, year = {2016}, volume = {50}, editor = {Raz, Ran}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.12}, URN = {urn:nbn:de:0030-drops-58400}, doi = {10.4230/LIPIcs.CCC.2016.12}, annote = {Keywords: Locally correctable code, Locally testable code, Affine Invariance, Gowers uniformity norm} }
Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)
Arnab Bhattacharyya, Victor Chen, Madhu Sudan, and Ning Xie. Testing Linear-Invariant Non-Linear Properties. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 135-146, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{bhattacharyya_et_al:LIPIcs.STACS.2009.1823, author = {Bhattacharyya, Arnab and Chen, Victor and Sudan, Madhu and Xie, Ning}, title = {{Testing Linear-Invariant Non-Linear Properties}}, booktitle = {26th International Symposium on Theoretical Aspects of Computer Science}, pages = {135--146}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-09-5}, ISSN = {1868-8969}, year = {2009}, volume = {3}, editor = {Albers, Susanne and Marion, Jean-Yves}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1823}, URN = {urn:nbn:de:0030-drops-18235}, doi = {10.4230/LIPIcs.STACS.2009.1823}, annote = {Keywords: } }