Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Josh Alman and Jarosław Błasiok. Matrix Multiplication and Number on the Forehead Communication. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 16:1-16:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{alman_et_al:LIPIcs.CCC.2023.16, author = {Alman, Josh and B{\l}asiok, Jaros{\l}aw}, title = {{Matrix Multiplication and Number on the Forehead Communication}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {16:1--16:23}, 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.16}, URN = {urn:nbn:de:0030-drops-182861}, doi = {10.4230/LIPIcs.CCC.2023.16}, annote = {Keywords: Number on the forehead, communication complexity, matrix multiplication} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Alexandr Andoni, Jarosław Błasiok, and Arnold Filtser. Communication Complexity of Inner Product in Symmetric Normed Spaces. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 4:1-4:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{andoni_et_al:LIPIcs.ITCS.2023.4, author = {Andoni, Alexandr and B{\l}asiok, Jaros{\l}aw and Filtser, Arnold}, title = {{Communication Complexity of Inner Product in Symmetric Normed Spaces}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {4:1--4:22}, 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.4}, URN = {urn:nbn:de:0030-drops-175077}, doi = {10.4230/LIPIcs.ITCS.2023.4}, annote = {Keywords: communication complexity, symmetric norms} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Jarosław Błasiok, Peter Ivanov, Yaonan Jin, Chin Ho Lee, Rocco A. Servedio, and Emanuele Viola. Fourier Growth of Structured 𝔽₂-Polynomials and Applications. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 53:1-53:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{blasiok_et_al:LIPIcs.APPROX/RANDOM.2021.53, author = {B{\l}asiok, Jaros{\l}aw and Ivanov, Peter and Jin, Yaonan and Lee, Chin Ho and Servedio, Rocco A. and Viola, Emanuele}, title = {{Fourier Growth of Structured \mathbb{F}₂-Polynomials and Applications}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {53:1--53: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.53}, URN = {urn:nbn:de:0030-drops-147462}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.53}, annote = {Keywords: Fourier analysis, Pseudorandomness, Fourier growth} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Emanuele Viola. Fourier Conjectures, Correlation Bounds, and Majority. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 111:1-111:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{viola:LIPIcs.ICALP.2021.111, author = {Viola, Emanuele}, title = {{Fourier Conjectures, Correlation Bounds, and Majority}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {111:1--111:15}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.111}, URN = {urn:nbn:de:0030-drops-141806}, doi = {10.4230/LIPIcs.ICALP.2021.111}, annote = {Keywords: Fourier analysis, polynomials, Majority, correlation, lower bound, conjectures} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Dean Doron, Jack Murtagh, Salil Vadhan, and David Zuckerman. Spectral Sparsification via Bounded-Independence Sampling. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 39:1-39:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{doron_et_al:LIPIcs.ICALP.2020.39, author = {Doron, Dean and Murtagh, Jack and Vadhan, Salil and Zuckerman, David}, title = {{Spectral Sparsification via Bounded-Independence Sampling}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {39:1--39:21}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.39}, URN = {urn:nbn:de:0030-drops-124462}, doi = {10.4230/LIPIcs.ICALP.2020.39}, annote = {Keywords: Spectral sparsification, Derandomization, Space complexity} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Chi-Ning Chou, Zhixian Lei, and Preetum Nakkiran. Tracking the l_2 Norm with Constant Update Time. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 2:1-2:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{chou_et_al:LIPIcs.APPROX-RANDOM.2019.2, author = {Chou, Chi-Ning and Lei, Zhixian and Nakkiran, Preetum}, title = {{Tracking the l\underline2 Norm with Constant Update Time}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {2:1--2:15}, 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.2}, URN = {urn:nbn:de:0030-drops-112175}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.2}, annote = {Keywords: Streaming algorithms, Sketching algorithms, Tracking, CountSketch} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Rohit Agrawal. Samplers and Extractors for Unbounded Functions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 59:1-59:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{agrawal:LIPIcs.APPROX-RANDOM.2019.59, author = {Agrawal, Rohit}, title = {{Samplers and Extractors for Unbounded Functions}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {59:1--59:21}, 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.59}, URN = {urn:nbn:de:0030-drops-112749}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.59}, annote = {Keywords: averaging samplers, subgaussian samplers, randomness extractors, Kullback-Leibler divergence} }
Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)
Jaroslaw Blasiok, Venkatesan Guruswami, and Madhu Sudan. Polar Codes with Exponentially Small Error at Finite Block Length. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 34:1-34:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{blasiok_et_al:LIPIcs.APPROX-RANDOM.2018.34, author = {Blasiok, Jaroslaw and Guruswami, Venkatesan and Sudan, Madhu}, title = {{Polar Codes with Exponentially Small Error at Finite Block Length}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)}, pages = {34:1--34:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-085-9}, ISSN = {1868-8969}, year = {2018}, volume = {116}, editor = {Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.34}, URN = {urn:nbn:de:0030-drops-94382}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2018.34}, annote = {Keywords: Polar codes, error exponent, rate of polarization} }
Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)
Jaroslaw Blasiok, Jian Ding, and Jelani Nelson. Continuous Monitoring of l_p Norms in Data Streams. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 32:1-32:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{blasiok_et_al:LIPIcs.APPROX-RANDOM.2017.32, author = {Blasiok, Jaroslaw and Ding, Jian and Nelson, Jelani}, title = {{Continuous Monitoring of l\underlinep Norms in Data Streams}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)}, pages = {32:1--32:13}, 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.32}, URN = {urn:nbn:de:0030-drops-75816}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2017.32}, annote = {Keywords: data streams, continuous monitoring, moment estimation} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Jaroslaw Blasiok and Jelani Nelson. An Improved Analysis of the ER-SpUD Dictionary Learning Algorithm. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 44:1-44:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{blasiok_et_al:LIPIcs.ICALP.2016.44, author = {Blasiok, Jaroslaw and Nelson, Jelani}, title = {{An Improved Analysis of the ER-SpUD Dictionary Learning Algorithm}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {44:1--44:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-013-2}, ISSN = {1868-8969}, year = {2016}, volume = {55}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.44}, URN = {urn:nbn:de:0030-drops-63246}, doi = {10.4230/LIPIcs.ICALP.2016.44}, annote = {Keywords: dictionary learning, stochastic processes, generic chaining} }
Feedback for Dagstuhl Publishing