Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Simon Apers, Paweł Gawrychowski, and Troy Lee. Finding the KT Partition of a Weighted Graph in Near-Linear Time. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 32:1-32:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{apers_et_al:LIPIcs.APPROX/RANDOM.2022.32, author = {Apers, Simon and Gawrychowski, Pawe{\l} and Lee, Troy}, title = {{Finding the KT Partition of a Weighted Graph in Near-Linear Time}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {32:1--32:14}, 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.32}, URN = {urn:nbn:de:0030-drops-171544}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.32}, annote = {Keywords: Graph theory} }
Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Sander Gribling and Harold Nieuwboer. Improved Quantum Lower and Upper Bounds for Matrix Scaling. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 35:1-35:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{gribling_et_al:LIPIcs.STACS.2022.35, author = {Gribling, Sander and Nieuwboer, Harold}, title = {{Improved Quantum Lower and Upper Bounds for Matrix Scaling}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {35:1--35:23}, 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.35}, URN = {urn:nbn:de:0030-drops-158458}, doi = {10.4230/LIPIcs.STACS.2022.35}, annote = {Keywords: Matrix scaling, quantum algorithms, lower bounds} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Troy Lee, Tongyang Li, Miklos Santha, and Shengyu Zhang. On the Cut Dimension of a Graph. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 15:1-15:35, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{lee_et_al:LIPIcs.CCC.2021.15, author = {Lee, Troy and Li, Tongyang and Santha, Miklos and Zhang, Shengyu}, title = {{On the Cut Dimension of a Graph}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {15:1--15:35}, 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.15}, URN = {urn:nbn:de:0030-drops-142890}, doi = {10.4230/LIPIcs.CCC.2021.15}, annote = {Keywords: Query complexity, submodular function minimization, cut dimension} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Simon Apers and Troy Lee. Quantum Complexity of Minimum Cut. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 28:1-28:33, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{apers_et_al:LIPIcs.CCC.2021.28, author = {Apers, Simon and Lee, Troy}, title = {{Quantum Complexity of Minimum Cut}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {28:1--28:33}, 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.28}, URN = {urn:nbn:de:0030-drops-143026}, doi = {10.4230/LIPIcs.CCC.2021.28}, annote = {Keywords: Quantum algorithms, quantum query complexity, minimum cut} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Srinivasan Arunachalam, Sourav Chakraborty, Troy Lee, Manaswi Paraashar, and Ronald de Wolf. Two New Results About Quantum Exact Learning. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 16:1-16:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{arunachalam_et_al:LIPIcs.ICALP.2019.16, author = {Arunachalam, Srinivasan and Chakraborty, Sourav and Lee, Troy and Paraashar, Manaswi and de Wolf, Ronald}, title = {{Two New Results About Quantum Exact Learning}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {16:1--16:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.16}, URN = {urn:nbn:de:0030-drops-105929}, doi = {10.4230/LIPIcs.ICALP.2019.16}, annote = {Keywords: quantum computing, exact learning, analysis of Boolean functions, Fourier sparse Boolean functions} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Dmitry Gavinsky, Troy Lee, Miklos Santha, and Swagato Sanyal. A Composition Theorem for Randomized Query Complexity via Max-Conflict Complexity. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 64:1-64:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{gavinsky_et_al:LIPIcs.ICALP.2019.64, author = {Gavinsky, Dmitry and Lee, Troy and Santha, Miklos and Sanyal, Swagato}, title = {{A Composition Theorem for Randomized Query Complexity via Max-Conflict Complexity}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {64:1--64:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.64}, URN = {urn:nbn:de:0030-drops-106407}, doi = {10.4230/LIPIcs.ICALP.2019.64}, annote = {Keywords: query complexity, lower bounds} }
Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Tom Bannink, Jop Briët, Harry Buhrman, Farrokh Labib, and Troy Lee. Bounding Quantum-Classical Separations for Classes of Nonlocal Games. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 12:1-12:11, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{bannink_et_al:LIPIcs.STACS.2019.12, author = {Bannink, Tom and Bri\"{e}t, Jop and Buhrman, Harry and Labib, Farrokh and Lee, Troy}, title = {{Bounding Quantum-Classical Separations for Classes of Nonlocal Games}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {12:1--12:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-100-9}, ISSN = {1868-8969}, year = {2019}, volume = {126}, editor = {Niedermeier, Rolf and Paul, Christophe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.12}, URN = {urn:nbn:de:0030-drops-102512}, doi = {10.4230/LIPIcs.STACS.2019.12}, annote = {Keywords: Nonlocal games, communication complexity, bounded separations, semidefinite programming, pseudorandomness, Gowers norms} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Troy Lee, Maharshi Ray, and Miklos Santha. Strategies for Quantum Races. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 51:1-51:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{lee_et_al:LIPIcs.ITCS.2019.51, author = {Lee, Troy and Ray, Maharshi and Santha, Miklos}, title = {{Strategies for Quantum Races}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {51:1--51:21}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.51}, URN = {urn:nbn:de:0030-drops-101446}, doi = {10.4230/LIPIcs.ITCS.2019.51}, annote = {Keywords: Game theory, Bitcoin mining, Quantum computing, Convex optimization} }
Published in: LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)
Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, and Swagato Sanyal. A Composition Theorem for Randomized Query Complexity. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 10:1-10:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{anshu_et_al:LIPIcs.FSTTCS.2017.10, author = {Anshu, Anurag and Gavinsky, Dmitry and Jain, Rahul and Kundu, Srijita and Lee, Troy and Mukhopadhyay, Priyanka and Santha, Miklos and Sanyal, Swagato}, title = {{A Composition Theorem for Randomized Query Complexity}}, booktitle = {37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)}, pages = {10:1--10:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-055-2}, ISSN = {1868-8969}, year = {2018}, volume = {93}, editor = {Lokam, Satya and Ramanujam, R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.10}, URN = {urn:nbn:de:0030-drops-83967}, doi = {10.4230/LIPIcs.FSTTCS.2017.10}, annote = {Keywords: Query algorithms and complexity, Decision trees, Composition theorem, XOR lemma, Hardness amplification} }
Published in: LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017)
Anurag Anshu, Shalev Ben-David, Ankit Garg, Rahul Jain, Robin Kothari, and Troy Lee. Separating Quantum Communication and Approximate Rank. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 24:1-24:33, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{anshu_et_al:LIPIcs.CCC.2017.24, author = {Anshu, Anurag and Ben-David, Shalev and Garg, Ankit and Jain, Rahul and Kothari, Robin and Lee, Troy}, title = {{Separating Quantum Communication and Approximate Rank}}, booktitle = {32nd Computational Complexity Conference (CCC 2017)}, pages = {24:1--24:33}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.24}, URN = {urn:nbn:de:0030-drops-75303}, doi = {10.4230/LIPIcs.CCC.2017.24}, annote = {Keywords: Communication Complexity, Quantum Computing, Lower Bounds, logrank, Quantum Information} }
Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)
Troy Lee, Anupam Prakash, Ronald de Wolf, and Henry Yuen. On the Sum-of-Squares Degree of Symmetric Quadratic Functions. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 17:1-17:31, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{lee_et_al:LIPIcs.CCC.2016.17, author = {Lee, Troy and Prakash, Anupam and de Wolf, Ronald and Yuen, Henry}, title = {{On the Sum-of-Squares Degree of Symmetric Quadratic Functions}}, booktitle = {31st Conference on Computational Complexity (CCC 2016)}, pages = {17:1--17:31}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-008-8}, ISSN = {1868-8969}, year = {2016}, volume = {50}, editor = {Raz, Ran}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.17}, URN = {urn:nbn:de:0030-drops-58383}, doi = {10.4230/LIPIcs.CCC.2016.17}, annote = {Keywords: Sum-of-squares degree, approximation theory, Positivstellensatz refutations of knapsack, quantum query complexity in expectation, extension complexity} }
Published in: DARTS, Volume 1, Issue 1, Special Issue of the 29th European Conference on Object-Oriented Programming (ECOOP 2015)
Joseph Lee, Jonathan Aldrich, Troy Shaw, Alex Potanin, and Benjamin Chung. A Theory of Tagged Objects (Artifact). In Special Issue of the 29th European Conference on Object-Oriented Programming (ECOOP 2015). Dagstuhl Artifacts Series (DARTS), Volume 1, Issue 1, pp. 3:1-3:3, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2015)
@Article{lee_et_al:DARTS.1.1.3, author = {Lee, Joseph and Aldrich, Jonathan and Shaw, Troy and Potanin, Alex and Chung, Benjamin}, title = {{A Theory of Tagged Objects (Artifact)}}, pages = {3:1--3:3}, journal = {Dagstuhl Artifacts Series}, ISSN = {2509-8195}, year = {2015}, volume = {1}, number = {1}, editor = {Lee, Joseph and Aldrich, Jonathan and Shaw, Troy and Potanin, Alex and Chung, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DARTS.1.1.3}, URN = {urn:nbn:de:0030-drops-55121}, doi = {10.4230/DARTS.1.1.3}, annote = {Keywords: objects, classes, tags, nominal and structural types} }
Published in: Dagstuhl Reports, Volume 5, Issue 2 (2015)
Hartmut Klauck, Troy Lee, Dirk Oliver Theis, and Rekha R. Thomas. Limitations of Convex Programming: Lower Bounds on Extended Formulations and Factorization Ranks (Dagstuhl Seminar 15082). In Dagstuhl Reports, Volume 5, Issue 2, pp. 109-127, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2015)
@Article{klauck_et_al:DagRep.5.2.109, author = {Klauck, Hartmut and Lee, Troy and Theis, Dirk Oliver and Thomas, Rekha R.}, title = {{Limitations of Convex Programming: Lower Bounds on Extended Formulations and Factorization Ranks (Dagstuhl Seminar 15082)}}, pages = {109--127}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2015}, volume = {5}, number = {2}, editor = {Klauck, Hartmut and Lee, Troy and Theis, Dirk Oliver and Thomas, Rekha R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.5.2.109}, URN = {urn:nbn:de:0030-drops-50480}, doi = {10.4230/DagRep.5.2.109}, annote = {Keywords: Convex optimization, extended formulations, cone rank, positive semidefinite rank, nonnegative rank, quantum communication complexity, real algebraic geometry} }
Published in: LIPIcs, Volume 37, 29th European Conference on Object-Oriented Programming (ECOOP 2015)
Joseph Lee, Jonathan Aldrich, Troy Shaw, and Alex Potanin. A Theory of Tagged Objects. In 29th European Conference on Object-Oriented Programming (ECOOP 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 37, pp. 174-197, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2015)
@InProceedings{lee_et_al:LIPIcs.ECOOP.2015.174, author = {Lee, Joseph and Aldrich, Jonathan and Shaw, Troy and Potanin, Alex}, title = {{A Theory of Tagged Objects}}, booktitle = {29th European Conference on Object-Oriented Programming (ECOOP 2015)}, pages = {174--197}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-86-6}, ISSN = {1868-8969}, year = {2015}, volume = {37}, editor = {Boyland, John Tang}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2015.174}, URN = {urn:nbn:de:0030-drops-52305}, doi = {10.4230/LIPIcs.ECOOP.2015.174}, annote = {Keywords: objects, classes, tags, nominal and structural types} }
Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Noga Alon, Troy Lee, and Adi Shraibman. The Cover Number of a Matrix and its Algorithmic Applications. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 34-47, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)
@InProceedings{alon_et_al:LIPIcs.APPROX-RANDOM.2014.34, author = {Alon, Noga and Lee, Troy and Shraibman, Adi}, title = {{The Cover Number of a Matrix and its Algorithmic Applications}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)}, pages = {34--47}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-74-3}, ISSN = {1868-8969}, year = {2014}, volume = {28}, editor = {Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.34}, URN = {urn:nbn:de:0030-drops-46865}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2014.34}, annote = {Keywords: Approximation algorithms, Approximate Nash equilibria, Cover number, VC dimension} }
Feedback for Dagstuhl Publishing