LIPIcs, Volume 45
FSTTCS 2015, December 16-18, 2015, Bangalore, India
Editors: Prahladh Harsha and G. Ramalingam
Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Prahladh Harsha, Tulasimohan Molli, and Ashutosh Shankar. Criticality of AC⁰-Formulae. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 19:1-19:24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{harsha_et_al:LIPIcs.CCC.2023.19, author = {Harsha, Prahladh and Molli, Tulasimohan and Shankar, Ashutosh}, title = {{Criticality of AC⁰-Formulae}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {19:1--19:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-282-2}, ISSN = {1868-8969}, year = {2023}, volume = {264}, editor = {Ta-Shma, Amnon}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.19}, URN = {urn:nbn:de:0030-drops-182898}, doi = {10.4230/LIPIcs.CCC.2023.19}, annote = {Keywords: AC⁰ circuits, AC⁰ formulae, criticality, switching lemma, correlation bounds} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Prahladh Harsha, Daniel Mitropolsky, and Alon Rosen. Downward Self-Reducibility in TFNP. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 67:1-67:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{harsha_et_al:LIPIcs.ITCS.2023.67, author = {Harsha, Prahladh and Mitropolsky, Daniel and Rosen, Alon}, title = {{Downward Self-Reducibility in TFNP}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {67:1--67:17}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.67}, URN = {urn:nbn:de:0030-drops-175700}, doi = {10.4230/LIPIcs.ITCS.2023.67}, annote = {Keywords: downward self-reducibility, TFNP, TFUP, factoring, PLS, CLS} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Siddharth Bhandari, Prahladh Harsha, Ramprasad Saptharishi, and Srikanth Srinivasan. Vanishing Spaces of Random Sets and Applications to Reed-Muller Codes. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 31:1-31:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{bhandari_et_al:LIPIcs.CCC.2022.31, author = {Bhandari, Siddharth and Harsha, Prahladh and Saptharishi, Ramprasad and Srinivasan, Srikanth}, title = {{Vanishing Spaces of Random Sets and Applications to Reed-Muller Codes}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {31:1--31:14}, 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.31}, URN = {urn:nbn:de:0030-drops-165934}, doi = {10.4230/LIPIcs.CCC.2022.31}, annote = {Keywords: Reed-Muller codes, polynomials, weight-distribution, vanishing ideals, erasures, capacity} }
Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Nikhil S. Mande, Swagato Sanyal, and Suhail Sherif. One-Way Communication Complexity and Non-Adaptive Decision Trees. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 49:1-49:24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{mande_et_al:LIPIcs.STACS.2022.49, author = {Mande, Nikhil S. and Sanyal, Swagato and Sherif, Suhail}, title = {{One-Way Communication Complexity and Non-Adaptive Decision Trees}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {49:1--49:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-222-8}, ISSN = {1868-8969}, year = {2022}, volume = {219}, editor = {Berenbrink, Petra and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.49}, URN = {urn:nbn:de:0030-drops-158598}, doi = {10.4230/LIPIcs.STACS.2022.49}, annote = {Keywords: Decision trees, communication complexity, composed Boolean functions} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Amey Bhangale, Prahladh Harsha, and Sourya Roy. Mixing of 3-Term Progressions in Quasirandom Groups. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 20:1-20:9, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{bhangale_et_al:LIPIcs.ITCS.2022.20, author = {Bhangale, Amey and Harsha, Prahladh and Roy, Sourya}, title = {{Mixing of 3-Term Progressions in Quasirandom Groups}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {20:1--20:9}, 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.20}, URN = {urn:nbn:de:0030-drops-156163}, doi = {10.4230/LIPIcs.ITCS.2022.20}, annote = {Keywords: Quasirandom groups, 3-term arithmetic progressions} }
Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)
Sourav Chakraborty, Nikhil S. Mande, Rajat Mittal, Tulasimohan Molli, Manaswi Paraashar, and Swagato Sanyal. Tight Chang’s-Lemma-Type Bounds for Boolean Functions. 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. 10:1-10:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{chakraborty_et_al:LIPIcs.FSTTCS.2021.10, author = {Chakraborty, Sourav and Mande, Nikhil S. and Mittal, Rajat and Molli, Tulasimohan and Paraashar, Manaswi and Sanyal, Swagato}, title = {{Tight Chang’s-Lemma-Type Bounds for Boolean Functions}}, booktitle = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)}, pages = {10:1--10:22}, 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.10}, URN = {urn:nbn:de:0030-drops-155215}, doi = {10.4230/LIPIcs.FSTTCS.2021.10}, annote = {Keywords: Analysis of Boolean functions, Chang’s lemma, Parity decision trees, Fourier dimension} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, and Madhu Sudan. Ideal-Theoretic Explanation of Capacity-Achieving Decoding. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 56:1-56:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{bhandari_et_al:LIPIcs.APPROX/RANDOM.2021.56, author = {Bhandari, Siddharth and Harsha, Prahladh and Kumar, Mrinal and Sudan, Madhu}, title = {{Ideal-Theoretic Explanation of Capacity-Achieving Decoding}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {56:1--56:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-207-5}, ISSN = {1868-8969}, year = {2021}, volume = {207}, editor = {Wootters, Mary and Sanit\`{a}, Laura}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.56}, URN = {urn:nbn:de:0030-drops-147499}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.56}, annote = {Keywords: List Decodability, List Decoding Capacity, Polynomial Ideal Codes, Multiplicity Codes, Folded Reed-Solomon Codes} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Irit Dinur, Yuval Filmus, Prahladh Harsha, and Madhur Tulsiani. Explicit SoS Lower Bounds from High-Dimensional Expanders. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 38:1-38:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{dinur_et_al:LIPIcs.ITCS.2021.38, author = {Dinur, Irit and Filmus, Yuval and Harsha, Prahladh and Tulsiani, Madhur}, title = {{Explicit SoS Lower Bounds from High-Dimensional Expanders}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {38:1--38:16}, 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.38}, URN = {urn:nbn:de:0030-drops-135774}, doi = {10.4230/LIPIcs.ITCS.2021.38}, annote = {Keywords: High-dimensional expanders, sum-of-squares, integrality gaps} }
Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)
Nikhil S. Mande and Swagato Sanyal. On Parity Decision Trees for Fourier-Sparse Boolean Functions. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 29:1-29:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{mande_et_al:LIPIcs.FSTTCS.2020.29, author = {Mande, Nikhil S. and Sanyal, Swagato}, title = {{On Parity Decision Trees for Fourier-Sparse Boolean Functions}}, booktitle = {40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)}, pages = {29:1--29:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-174-0}, ISSN = {1868-8969}, year = {2020}, volume = {182}, editor = {Saxena, Nitin and Simon, Sunil}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.29}, URN = {urn:nbn:de:0030-drops-132703}, doi = {10.4230/LIPIcs.FSTTCS.2020.29}, annote = {Keywords: Parity decision trees, log-rank conjecture, analysis of Boolean functions, communication complexity} }
Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Abhishek Bhrushundi, Prahladh Harsha, Pooya Hatami, Swastik Kopparty, and Mrinal Kumar. On Multilinear Forms: Bias, Correlation, and Tensor Rank. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 29:1-29:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{bhrushundi_et_al:LIPIcs.APPROX/RANDOM.2020.29, author = {Bhrushundi, Abhishek and Harsha, Prahladh and Hatami, Pooya and Kopparty, Swastik and Kumar, Mrinal}, title = {{On Multilinear Forms: Bias, Correlation, and Tensor Rank}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)}, pages = {29:1--29:23}, 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.29}, URN = {urn:nbn:de:0030-drops-126325}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.29}, annote = {Keywords: polynomials, Boolean functions, tensor rank, bias, correlation} }
Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Venkatesan Guruswami, Jakub Opršal, and Sai Sandeep. Revisiting Alphabet Reduction in Dinur’s PCP. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 34:1-34:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{guruswami_et_al:LIPIcs.APPROX/RANDOM.2020.34, author = {Guruswami, Venkatesan and Opr\v{s}al, Jakub and Sandeep, Sai}, title = {{Revisiting Alphabet Reduction in Dinur’s PCP}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)}, pages = {34:1--34:14}, 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.34}, URN = {urn:nbn:de:0030-drops-126372}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.34}, annote = {Keywords: PCP theorem, CSP, discrete Fourier analysis, label cover, long code} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Aaron Potechin. Sum of Squares Bounds for the Ordering Principle. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 38:1-38:37, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{potechin:LIPIcs.CCC.2020.38, author = {Potechin, Aaron}, title = {{Sum of Squares Bounds for the Ordering Principle}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {38:1--38:37}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-156-6}, ISSN = {1868-8969}, year = {2020}, volume = {169}, editor = {Saraf, Shubhangi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.38}, URN = {urn:nbn:de:0030-drops-125900}, doi = {10.4230/LIPIcs.CCC.2020.38}, annote = {Keywords: sum of squares hierarchy, proof complexity, ordering principle} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Prahladh Harsha, Subhash Khot, Euiwoong Lee, and Devanathan Thiruvenkatachari. Improved 3LIN Hardness via Linear Label Cover. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 9:1-9:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{harsha_et_al:LIPIcs.APPROX-RANDOM.2019.9, author = {Harsha, Prahladh and Khot, Subhash and Lee, Euiwoong and Thiruvenkatachari, Devanathan}, title = {{Improved 3LIN Hardness via Linear Label Cover}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {9:1--9:16}, 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.9}, URN = {urn:nbn:de:0030-drops-112245}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.9}, annote = {Keywords: probabilistically checkable proofs, PCP, composition, 3LIN, low soundness error} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Rocco A. Servedio and Li-Yang Tan. Improved Pseudorandom Generators from Pseudorandom Multi-Switching Lemmas. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 45:1-45:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{servedio_et_al:LIPIcs.APPROX-RANDOM.2019.45, author = {Servedio, Rocco A. and Tan, Li-Yang}, title = {{Improved Pseudorandom Generators from Pseudorandom Multi-Switching Lemmas}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {45:1--45:23}, 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.45}, URN = {urn:nbn:de:0030-drops-112605}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.45}, annote = {Keywords: pseudorandom generators, switching lemmas, circuit complexity, unconditional derandomization} }
Feedback for Dagstuhl Publishing