Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, and Rocco A. Servedio. Testing Intersecting and Union-Closed Families. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 33:1-33:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chen_et_al:LIPIcs.ITCS.2024.33, author = {Chen, Xi and De, Anindya and Li, Yuhao and Nadimpalli, Shivam and Servedio, Rocco A.}, title = {{Testing Intersecting and Union-Closed Families}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {33:1--33:23}, 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.33}, URN = {urn:nbn:de:0030-drops-195610}, doi = {10.4230/LIPIcs.ITCS.2024.33}, annote = {Keywords: Sublinear algorithms, property testing, computational complexity, monotonicity, intersecting families, union-closed families} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Xin Lyu. Improved Pseudorandom Generators for AC⁰ Circuits. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 34:1-34:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{lyu:LIPIcs.CCC.2022.34, author = {Lyu, Xin}, title = {{Improved Pseudorandom Generators for AC⁰ Circuits}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {34:1--34:25}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.34}, URN = {urn:nbn:de:0030-drops-165963}, doi = {10.4230/LIPIcs.CCC.2022.34}, annote = {Keywords: pseudorandom generators, derandomization, switching Lemmas, AC⁰} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Anindya De, Shivam Nadimpalli, and Rocco A. Servedio. Convex Influences. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 53:1-53:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{de_et_al:LIPIcs.ITCS.2022.53, author = {De, Anindya and Nadimpalli, Shivam and Servedio, Rocco A.}, title = {{Convex Influences}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {53:1--53: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.53}, URN = {urn:nbn:de:0030-drops-156498}, doi = {10.4230/LIPIcs.ITCS.2022.53}, annote = {Keywords: Fourier analysis of Boolean functions, convex geometry, influences, threshold phenomena} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Vishnu Iyer, Avishay Tal, and Michael Whitmeyer. Junta Distance Approximation with Sub-Exponential Queries. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 24:1-24:38, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{iyer_et_al:LIPIcs.CCC.2021.24, author = {Iyer, Vishnu and Tal, Avishay and Whitmeyer, Michael}, title = {{Junta Distance Approximation with Sub-Exponential Queries}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {24:1--24:38}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.24}, URN = {urn:nbn:de:0030-drops-142988}, doi = {10.4230/LIPIcs.CCC.2021.24}, annote = {Keywords: Algorithms, Complexity Theory, Fourier Analysis, Juntas, Normalized Influence, Property Testing, Tolerant Property Testing} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Sharat Ibrahimpur and Chaitanya Swamy. Minimum-Norm Load Balancing Is (Almost) as Easy as Minimizing Makespan. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 81:1-81:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{ibrahimpur_et_al:LIPIcs.ICALP.2021.81, author = {Ibrahimpur, Sharat and Swamy, Chaitanya}, title = {{Minimum-Norm Load Balancing Is (Almost) as Easy as Minimizing Makespan}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {81:1--81:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.81}, URN = {urn:nbn:de:0030-drops-141504}, doi = {10.4230/LIPIcs.ICALP.2021.81}, annote = {Keywords: Approximation algorithms, Load balancing, Minimum-norm optimization, LP rounding} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, and Sandip Sinha. Polynomial-Time Trace Reconstruction in the Low Deletion Rate Regime. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 20:1-20:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{chen_et_al:LIPIcs.ITCS.2021.20, author = {Chen, Xi and De, Anindya and Lee, Chin Ho and Servedio, Rocco A. and Sinha, Sandip}, title = {{Polynomial-Time Trace Reconstruction in the Low Deletion Rate Regime}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {20:1--20:20}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.20}, URN = {urn:nbn:de:0030-drops-135595}, doi = {10.4230/LIPIcs.ITCS.2021.20}, annote = {Keywords: trace reconstruction} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Anindya De, Shivam Nadimpalli, and Rocco A. Servedio. Quantitative Correlation Inequalities via Semigroup Interpolation. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 69:1-69:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{de_et_al:LIPIcs.ITCS.2021.69, author = {De, Anindya and Nadimpalli, Shivam and Servedio, Rocco A.}, title = {{Quantitative Correlation Inequalities via Semigroup Interpolation}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {69:1--69:20}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.69}, URN = {urn:nbn:de:0030-drops-136081}, doi = {10.4230/LIPIcs.ITCS.2021.69}, annote = {Keywords: complex analysis, correlation inequality, FKG inequality, Gaussian correlation inequality, harmonic analysis, Markov semigroups} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Anindya De, Sanjeev Khanna, Huan Li, and Hesam Nikpey. An Efficient PTAS for Stochastic Load Balancing with Poisson Jobs. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 37:1-37:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{de_et_al:LIPIcs.ICALP.2020.37, author = {De, Anindya and Khanna, Sanjeev and Li, Huan and Nikpey, Hesam}, title = {{An Efficient PTAS for Stochastic Load Balancing with Poisson Jobs}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {37:1--37:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.37}, URN = {urn:nbn:de:0030-drops-124449}, doi = {10.4230/LIPIcs.ICALP.2020.37}, annote = {Keywords: Efficient PTAS, Makespan Minimization, Scheduling, Stochastic Load Balancing, Poisson Distribution} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Eshan Chattopadhyay, Anindya De, and Rocco A. Servedio. Simple and Efficient Pseudorandom Generators from Gaussian Processes. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 4:1-4:33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{chattopadhyay_et_al:LIPIcs.CCC.2019.4, author = {Chattopadhyay, Eshan and De, Anindya and Servedio, Rocco A.}, title = {{Simple and Efficient Pseudorandom Generators from Gaussian Processes}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {4:1--4:33}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.4}, URN = {urn:nbn:de:0030-drops-108262}, doi = {10.4230/LIPIcs.CCC.2019.4}, annote = {Keywords: Polynomial threshold functions, Gaussian processes, Johnson-Lindenstrauss, pseudorandom generators} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Anindya De, Philip M. Long, and Rocco A. Servedio. Density Estimation for Shift-Invariant Multidimensional Distributions. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 28:1-28:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{de_et_al:LIPIcs.ITCS.2019.28, author = {De, Anindya and Long, Philip M. and Servedio, Rocco A.}, title = {{Density Estimation for Shift-Invariant Multidimensional Distributions}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {28:1--28:20}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.28}, URN = {urn:nbn:de:0030-drops-101214}, doi = {10.4230/LIPIcs.ITCS.2019.28}, annote = {Keywords: Density estimation, unsupervised learning, log-concave distributions, non-parametrics} }
Published in: LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017)
Anindya De, Elchanan Mossel, and Joe Neeman. Noise Stability Is Computable and Approximately Low-Dimensional. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 10:1-10:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{de_et_al:LIPIcs.CCC.2017.10, author = {De, Anindya and Mossel, Elchanan and Neeman, Joe}, title = {{Noise Stability Is Computable and Approximately Low-Dimensional}}, booktitle = {32nd Computational Complexity Conference (CCC 2017)}, pages = {10:1--10:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-040-8}, ISSN = {1868-8969}, year = {2017}, volume = {79}, editor = {O'Donnell, Ryan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.10}, URN = {urn:nbn:de:0030-drops-75390}, doi = {10.4230/LIPIcs.CCC.2017.10}, annote = {Keywords: Gaussian noise stability; Plurality is stablest; Ornstein Uhlenbeck operator} }
Published in: DARTS, Volume 3, Issue 2, Special Issue of the 31st European Conference on Object-Oriented Programming (ECOOP 2017)
Germán Andrés Delbianco, Ilya Sergey, Aleksandar Nanevski, and Anindya Banerjee. Concurrent Data Structures Linked in Time (Artifact). In Special Issue of the 31st European Conference on Object-Oriented Programming (ECOOP 2017). Dagstuhl Artifacts Series (DARTS), Volume 3, Issue 2, pp. 4:1-4:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@Article{delbianco_et_al:DARTS.3.2.4, author = {Delbianco, Germ\'{a}n Andr\'{e}s and Sergey, Ilya and Nanevski, Aleksandar and Banerjee, Anindya}, title = {{Concurrent Data Structures Linked in Time (Artifact)}}, pages = {4:1--4:4}, journal = {Dagstuhl Artifacts Series}, ISSN = {2509-8195}, year = {2017}, volume = {3}, number = {2}, editor = {Delbianco, Germ\'{a}n Andr\'{e}s and Sergey, Ilya and Nanevski, Aleksandar and Banerjee, Anindya}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DARTS.3.2.4}, URN = {urn:nbn:de:0030-drops-72850}, doi = {10.4230/DARTS.3.2.4}, annote = {Keywords: separation logic, linearization Points, concurrent snapshots, FCSL} }
Feedback for Dagstuhl Publishing