Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Nikhil Bansal, Makrand Sinha, and Ronald de Wolf. Influence in Completely Bounded Block-Multilinear Forms and Classical Simulation of Quantum Algorithms. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 28:1-28:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{bansal_et_al:LIPIcs.CCC.2022.28, author = {Bansal, Nikhil and Sinha, Makrand and de Wolf, Ronald}, title = {{Influence in Completely Bounded Block-Multilinear Forms and Classical Simulation of Quantum Algorithms}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {28:1--28:21}, 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.28}, URN = {urn:nbn:de:0030-drops-165908}, doi = {10.4230/LIPIcs.CCC.2022.28}, annote = {Keywords: Aaronson-Ambainis conjecture, Quantum query complexity, Classical query complexity, Free probability, Completely bounded norm, Analysis of Boolean functions, Influence} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, and Makrand Sinha. Smoothed Analysis of the Komlós Conjecture. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 14:1-14:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{bansal_et_al:LIPIcs.ICALP.2022.14, author = {Bansal, Nikhil and Jiang, Haotian and Meka, Raghu and Singla, Sahil and Sinha, Makrand}, title = {{Smoothed Analysis of the Koml\'{o}s Conjecture}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {14:1--14:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.14}, URN = {urn:nbn:de:0030-drops-163556}, doi = {10.4230/LIPIcs.ICALP.2022.14}, annote = {Keywords: Koml\'{o}s conjecture, smoothed analysis, weighted second moment method, subgaussian coloring} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, and Makrand Sinha. Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 13:1-13:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{bansal_et_al:LIPIcs.ITCS.2022.13, author = {Bansal, Nikhil and Jiang, Haotian and Meka, Raghu and Singla, Sahil and Sinha, Makrand}, title = {{Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {13:1--13:22}, 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.13}, URN = {urn:nbn:de:0030-drops-156092}, doi = {10.4230/LIPIcs.ITCS.2022.13}, annote = {Keywords: Prefix discrepancy, smoothed analysis, combinatorial vector balancing} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Sander Borst, Daniel Dadush, Neil Olver, and Makrand Sinha. Majorizing Measures for the Optimizer. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 73:1-73:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{borst_et_al:LIPIcs.ITCS.2021.73, author = {Borst, Sander and Dadush, Daniel and Olver, Neil and Sinha, Makrand}, title = {{Majorizing Measures for the Optimizer}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {73:1--73: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.73}, URN = {urn:nbn:de:0030-drops-136120}, doi = {10.4230/LIPIcs.ITCS.2021.73}, annote = {Keywords: Majorizing measures, Generic chaining, Gaussian processes, Convex optimization, Dimensionality Reduction} }
Published in: LIPIcs, Volume 158, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)
João F. Doriguello and Ashley Montanaro. Exponential Quantum Communication Reductions from Generalizations of the Boolean Hidden Matching Problem. In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 158, pp. 1:1-1:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{doriguello_et_al:LIPIcs.TQC.2020.1, author = {Doriguello, Jo\~{a}o F. and Montanaro, Ashley}, title = {{Exponential Quantum Communication Reductions from Generalizations of the Boolean Hidden Matching Problem}}, booktitle = {15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)}, pages = {1:1--1:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-146-7}, ISSN = {1868-8969}, year = {2020}, volume = {158}, editor = {Flammia, Steven T.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2020.1}, URN = {urn:nbn:de:0030-drops-120601}, doi = {10.4230/LIPIcs.TQC.2020.1}, annote = {Keywords: Communication Complexity, Quantum Communication Complexity, Boolean Hidden Matching Problem} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Sivaramakrishnan Natarajan Ramamoorthy and Cyrus Rashtchian. Equivalence of Systematic Linear Data Structures and Matrix Rigidity. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 35:1-35:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{natarajanramamoorthy_et_al:LIPIcs.ITCS.2020.35, author = {Natarajan Ramamoorthy, Sivaramakrishnan and Rashtchian, Cyrus}, title = {{Equivalence of Systematic Linear Data Structures and Matrix Rigidity}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {35:1--35:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-134-4}, ISSN = {1868-8969}, year = {2020}, volume = {151}, editor = {Vidick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.35}, URN = {urn:nbn:de:0030-drops-117204}, doi = {10.4230/LIPIcs.ITCS.2020.35}, annote = {Keywords: matrix rigidity, systematic linear data structures, cell probe model, communication complexity} }
Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Paul Beame, Sariel Har-Peled, Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian, and Makrand Sinha. Edge Estimation with Independent Set Oracles. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 38:1-38:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{beame_et_al:LIPIcs.ITCS.2018.38, author = {Beame, Paul and Har-Peled, Sariel and Natarajan Ramamoorthy, Sivaramakrishnan and Rashtchian, Cyrus and Sinha, Makrand}, title = {{Edge Estimation with Independent Set Oracles}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, pages = {38:1--38:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-060-6}, ISSN = {1868-8969}, year = {2018}, volume = {94}, editor = {Karlin, Anna R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.38}, URN = {urn:nbn:de:0030-drops-83552}, doi = {10.4230/LIPIcs.ITCS.2018.38}, annote = {Keywords: Approximate Counting, Independent Set Queries, Sparsification, Importance Sampling} }
Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Anup Rao and Makrand Sinha. A Direct-Sum Theorem for Read-Once Branching Programs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 44:1-44:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{rao_et_al:LIPIcs.APPROX-RANDOM.2016.44, author = {Rao, Anup and Sinha, Makrand}, title = {{A Direct-Sum Theorem for Read-Once Branching Programs}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)}, pages = {44:1--44:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-018-7}, ISSN = {1868-8969}, year = {2016}, volume = {60}, editor = {Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.44}, URN = {urn:nbn:de:0030-drops-66676}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2016.44}, annote = {Keywords: Direct-sum, Information complexity, Streaming Algorithms} }
Feedback for Dagstuhl Publishing