Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Prashanth Amireddy, Srikanth Srinivasan, and Madhu Sudan. Low-Degree Testing over Grids. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 41:1-41:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{amireddy_et_al:LIPIcs.APPROX/RANDOM.2023.41, author = {Amireddy, Prashanth and Srinivasan, Srikanth and Sudan, Madhu}, title = {{Low-Degree Testing over Grids}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {41:1--41:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-296-9}, ISSN = {1868-8969}, year = {2023}, volume = {275}, editor = {Megow, Nicole and Smith, Adam}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.41}, URN = {urn:nbn:de:0030-drops-188665}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.41}, annote = {Keywords: Property testing, Low-degree testing, Small-set expansion, Local testing} }
Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Deepanshu Kush and Shubhangi Saraf. Near-Optimal Set-Multilinear Formula Lower Bounds. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 15:1-15:33, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{kush_et_al:LIPIcs.CCC.2023.15, author = {Kush, Deepanshu and Saraf, Shubhangi}, title = {{Near-Optimal Set-Multilinear Formula Lower Bounds}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {15:1--15:33}, 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.15}, URN = {urn:nbn:de:0030-drops-182855}, doi = {10.4230/LIPIcs.CCC.2023.15}, annote = {Keywords: Algebraic Complexity, Set-multilinear, Formula Lower Bounds} }
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 264, 38th Computational Complexity Conference (CCC 2023)
Hervé Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan, and Sébastien Tavenas. Towards Optimal Depth-Reductions for Algebraic Formulas. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 28:1-28:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{fournier_et_al:LIPIcs.CCC.2023.28, author = {Fournier, Herv\'{e} and Limaye, Nutan and Malod, Guillaume and Srinivasan, Srikanth and Tavenas, S\'{e}bastien}, title = {{Towards Optimal Depth-Reductions for Algebraic Formulas}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {28:1--28:19}, 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.28}, URN = {urn:nbn:de:0030-drops-182986}, doi = {10.4230/LIPIcs.CCC.2023.28}, annote = {Keywords: Algebraic formulas, depth-reduction} }
Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Rahul Santhanam. An Algorithmic Approach to Uniform Lower Bounds. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 35:1-35:26, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{santhanam:LIPIcs.CCC.2023.35, author = {Santhanam, Rahul}, title = {{An Algorithmic Approach to Uniform Lower Bounds}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {35:1--35:26}, 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.35}, URN = {urn:nbn:de:0030-drops-183053}, doi = {10.4230/LIPIcs.CCC.2023.35}, annote = {Keywords: Probabilistic Kolmogorov complexity, sampling algorithms, uniform lower bounds} }
Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)
Radu Curticapean, Nutan Limaye, and Srikanth Srinivasan. On the VNP-Hardness of Some Monomial Symmetric Polynomials. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 16:1-16:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{curticapean_et_al:LIPIcs.FSTTCS.2022.16, author = {Curticapean, Radu and Limaye, Nutan and Srinivasan, Srikanth}, title = {{On the VNP-Hardness of Some Monomial Symmetric Polynomials}}, booktitle = {42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)}, pages = {16:1--16:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-261-7}, ISSN = {1868-8969}, year = {2022}, volume = {250}, editor = {Dawar, Anuj and Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.16}, URN = {urn:nbn:de:0030-drops-174081}, doi = {10.4230/LIPIcs.FSTTCS.2022.16}, annote = {Keywords: algebraic complexity, symmetric polynomial, permanent, Sidon set} }
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 234, 37th Computational Complexity Conference (CCC 2022)
Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas. On the Partial Derivative Method Applied to Lopsided Set-Multilinear Polynomials. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 32:1-32:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{limaye_et_al:LIPIcs.CCC.2022.32, author = {Limaye, Nutan and Srinivasan, Srikanth and Tavenas, S\'{e}bastien}, title = {{On the Partial Derivative Method Applied to Lopsided Set-Multilinear Polynomials}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {32:1--32:23}, 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.32}, URN = {urn:nbn:de:0030-drops-165942}, doi = {10.4230/LIPIcs.CCC.2022.32}, annote = {Keywords: Partial Derivative Method, Barriers to Lower Bounds} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Arkadev Chattopadhyay, Rajit Datta, Utsab Ghosal, and Partha Mukhopadhyay. Monotone Complexity of Spanning Tree Polynomial Re-Visited. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 39:1-39:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{chattopadhyay_et_al:LIPIcs.ITCS.2022.39, author = {Chattopadhyay, Arkadev and Datta, Rajit and Ghosal, Utsab and Mukhopadhyay, Partha}, title = {{Monotone Complexity of Spanning Tree Polynomial Re-Visited}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {39:1--39:21}, 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.39}, URN = {urn:nbn:de:0030-drops-156356}, doi = {10.4230/LIPIcs.ITCS.2022.39}, annote = {Keywords: Spanning Tree Polynomial, Monotone Computation, Lower Bounds, Communication Complexity} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Srikanth Srinivasan and S. Venkitesh. On the Probabilistic Degree of an n-Variate Boolean Function. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 42:1-42:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{srinivasan_et_al:LIPIcs.APPROX/RANDOM.2021.42, author = {Srinivasan, Srikanth and Venkitesh, S.}, title = {{On the Probabilistic Degree of an n-Variate Boolean Function}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {42:1--42:20}, 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.42}, URN = {urn:nbn:de:0030-drops-147356}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.42}, annote = {Keywords: truly n-variate, Boolean function, probabilistic polynomial, probabilistic degree} }
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 169, 35th Computational Complexity Conference (CCC 2020)
Mrinal Kumar and Ben Lee Volk. Lower Bounds for Matrix Factorization. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 5:1-5:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{kumar_et_al:LIPIcs.CCC.2020.5, author = {Kumar, Mrinal and Volk, Ben Lee}, title = {{Lower Bounds for Matrix Factorization}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {5:1--5:20}, 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.5}, URN = {urn:nbn:de:0030-drops-125578}, doi = {10.4230/LIPIcs.CCC.2020.5}, annote = {Keywords: Algebraic Complexity, Linear Circuits, Matrix Factorization, Lower Bounds} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Prasad Chaugule, Mrinal Kumar, Nutan Limaye, Chandra Kanta Mohapatra, Adrian She, and Srikanth Srinivasan. Schur Polynomials Do Not Have Small Formulas If the Determinant Doesn't. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 14:1-14:27, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{chaugule_et_al:LIPIcs.CCC.2020.14, author = {Chaugule, Prasad and Kumar, Mrinal and Limaye, Nutan and Mohapatra, Chandra Kanta and She, Adrian and Srinivasan, Srikanth}, title = {{Schur Polynomials Do Not Have Small Formulas If the Determinant Doesn't}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {14:1--14:27}, 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.14}, URN = {urn:nbn:de:0030-drops-125660}, doi = {10.4230/LIPIcs.CCC.2020.14}, annote = {Keywords: Schur polynomial, Jacobian, Algebraic independence, Generalized Vandermonde determinant, Taylor expansion, Formula complexity, Lower bound} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Yuval Filmus, Yuval Ishai, Avi Kaplan, and Guy Kindler. Limits of Preprocessing. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 17:1-17:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{filmus_et_al:LIPIcs.CCC.2020.17, author = {Filmus, Yuval and Ishai, Yuval and Kaplan, Avi and Kindler, Guy}, title = {{Limits of Preprocessing}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {17:1--17:22}, 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.17}, URN = {urn:nbn:de:0030-drops-125697}, doi = {10.4230/LIPIcs.CCC.2020.17}, annote = {Keywords: circuit, communication complexity, IPPP, preprocessing, PRF, simultaneous messages} }
Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Suryajith Chillara. On Computing Multilinear Polynomials Using Multi-r-ic Depth Four Circuits. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 47:1-47:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{chillara:LIPIcs.STACS.2020.47, author = {Chillara, Suryajith}, title = {{On Computing Multilinear Polynomials Using Multi-r-ic Depth Four Circuits}}, booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, pages = {47:1--47:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-140-5}, ISSN = {1868-8969}, year = {2020}, volume = {154}, editor = {Paul, Christophe and Bl\"{a}ser, Markus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.47}, URN = {urn:nbn:de:0030-drops-119084}, doi = {10.4230/LIPIcs.STACS.2020.47}, annote = {Keywords: Lower Bounds, Multilinear, Multi-r-ic} }
Feedback for Dagstuhl Publishing