Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Vladimir V. Podolskii and Dmitrii Sluch. One-Way Communication Complexity of Partial XOR Functions. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 116:1-116:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{podolskii_et_al:LIPIcs.ICALP.2024.116, author = {Podolskii, Vladimir V. and Sluch, Dmitrii}, title = {{One-Way Communication Complexity of Partial XOR Functions}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {116:1--116:16}, 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.116}, URN = {urn:nbn:de:0030-drops-202591}, doi = {10.4230/LIPIcs.ICALP.2024.116}, annote = {Keywords: Partial functions, XOR functions, communication complexity, decision trees, covering codes} }
Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Srinivasan Arunachalam and Uma Girish. Trade-Offs Between Entanglement and Communication. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 25:1-25:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{arunachalam_et_al:LIPIcs.CCC.2023.25, author = {Arunachalam, Srinivasan and Girish, Uma}, title = {{Trade-Offs Between Entanglement and Communication}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {25:1--25: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.25}, URN = {urn:nbn:de:0030-drops-182957}, doi = {10.4230/LIPIcs.CCC.2023.25}, annote = {Keywords: quantum, communication complexity, exponential separation, boolean hidden matching, forrelation, xor lemma} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Uma Girish, Ran Raz, and Wei Zhan. Is Untrusted Randomness Helpful?. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 56:1-56:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{girish_et_al:LIPIcs.ITCS.2023.56, author = {Girish, Uma and Raz, Ran and Zhan, Wei}, title = {{Is Untrusted Randomness Helpful?}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {56:1--56:18}, 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.56}, URN = {urn:nbn:de:0030-drops-175593}, doi = {10.4230/LIPIcs.ITCS.2023.56}, annote = {Keywords: Untrusted, Randomness, Verifiable, ZPL, BPL, ZPP, BPP} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Uma Girish, Kunal Mittal, Ran Raz, and Wei Zhan. Polynomial Bounds on Parallel Repetition for All 3-Player Games with Binary Inputs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 6:1-6:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{girish_et_al:LIPIcs.APPROX/RANDOM.2022.6, author = {Girish, Uma and Mittal, Kunal and Raz, Ran and Zhan, Wei}, title = {{Polynomial Bounds on Parallel Repetition for All 3-Player Games with Binary Inputs}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {6:1--6:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-249-5}, ISSN = {1868-8969}, year = {2022}, volume = {245}, editor = {Chakrabarti, Amit and Swamy, Chaitanya}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.6}, URN = {urn:nbn:de:0030-drops-171286}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.6}, annote = {Keywords: Parallel repetition, Multi-prover games, Fourier analysis} }
Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Xinyu Wu. Analyzing XOR-Forrelation Through Stochastic Calculus. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 60:1-60:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{wu:LIPIcs.STACS.2022.60, author = {Wu, Xinyu}, title = {{Analyzing XOR-Forrelation Through Stochastic Calculus}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {60:1--60:7}, 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.60}, URN = {urn:nbn:de:0030-drops-158705}, doi = {10.4230/LIPIcs.STACS.2022.60}, annote = {Keywords: quantum complexity, Brownian motion} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Uma Girish and Ran Raz. Eliminating Intermediate Measurements Using Pseudorandom Generators. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 76:1-76:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{girish_et_al:LIPIcs.ITCS.2022.76, author = {Girish, Uma and Raz, Ran}, title = {{Eliminating Intermediate Measurements Using Pseudorandom Generators}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {76:1--76:18}, 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.76}, URN = {urn:nbn:de:0030-drops-156726}, doi = {10.4230/LIPIcs.ITCS.2022.76}, annote = {Keywords: quantum algorithms, intermediate measurements, deferred measurement, pseudorandom generator, INW generator} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Uma Girish, Ran Raz, and Wei Zhan. Lower Bounds for XOR of Forrelations. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 52:1-52:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{girish_et_al:LIPIcs.APPROX/RANDOM.2021.52, author = {Girish, Uma and Raz, Ran and Zhan, Wei}, title = {{Lower Bounds for XOR of Forrelations}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {52:1--52:14}, 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.52}, URN = {urn:nbn:de:0030-drops-147453}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.52}, annote = {Keywords: Forrelation, Quasipolynomial, Separation, Quantum versus Classical, Xor} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Uma Girish, Justin Holmgren, Kunal Mittal, Ran Raz, and Wei Zhan. Parallel Repetition for the GHZ Game: A Simpler Proof. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 62:1-62:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{girish_et_al:LIPIcs.APPROX/RANDOM.2021.62, author = {Girish, Uma and Holmgren, Justin and Mittal, Kunal and Raz, Ran and Zhan, Wei}, title = {{Parallel Repetition for the GHZ Game: A Simpler Proof}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {62:1--62:19}, 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.62}, URN = {urn:nbn:de:0030-drops-147551}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.62}, annote = {Keywords: Parallel Repetition, GHZ, Polynomial, Multi-player} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Uma Girish, Avishay Tal, and Kewen Wu. Fourier Growth of Parity Decision Trees. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 39:1-39:36, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{girish_et_al:LIPIcs.CCC.2021.39, author = {Girish, Uma and Tal, Avishay and Wu, Kewen}, title = {{Fourier Growth of Parity Decision Trees}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {39:1--39:36}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.39}, URN = {urn:nbn:de:0030-drops-143137}, doi = {10.4230/LIPIcs.CCC.2021.39}, annote = {Keywords: Fourier analysis of Boolean functions, noisy decision tree, parity decision tree, query complexity} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Uma Girish, Ran Raz, and Wei Zhan. Quantum Logspace Algorithm for Powering Matrices with Bounded Norm. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 73:1-73:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{girish_et_al:LIPIcs.ICALP.2021.73, author = {Girish, Uma and Raz, Ran and Zhan, Wei}, title = {{Quantum Logspace Algorithm for Powering Matrices with Bounded Norm}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {73:1--73: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.73}, URN = {urn:nbn:de:0030-drops-141426}, doi = {10.4230/LIPIcs.ICALP.2021.73}, annote = {Keywords: BQL, Matrix Powering, Quantum Circuit, Reversible Computation} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Uma Girish, Ran Raz, and Avishay Tal. Quantum Versus Randomized Communication Complexity, with Efficient Players. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 54:1-54:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{girish_et_al:LIPIcs.ITCS.2021.54, author = {Girish, Uma and Raz, Ran and Tal, Avishay}, title = {{Quantum Versus Randomized Communication Complexity, with Efficient Players}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {54:1--54: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.54}, URN = {urn:nbn:de:0030-drops-135932}, doi = {10.4230/LIPIcs.ITCS.2021.54}, annote = {Keywords: Exponential Separation, Quantum, Randomized, Communication, Complexity, Forrelation} }
Feedback for Dagstuhl Publishing