Troy Lee - RankMe

107 papers A* 11A 16B 1C 1Misc 1Journal 67Unranked 9

Year	Rank	Type	Title / Venue / Authors
2025	J	`jnl`	Introduction: ACM-SIAM Symposium on Discrete Algorithms (SODA) 2021 Special Issue. ACM Trans. Algorithms Alina Ene, Troy Lee, Piotr Micek, Sushant Sachdeva
2025	A*	`conf`	On the Quantum Time Complexity of Divide and Conquer. ICALP Jonathan Allcock, Jinge Bao, Aleksandrs Belovs, Troy Lee, Miklos Santha
2023	J	`jnl`	On the quantum time complexity of divide and conquer. CoRR Jonathan Allcock, Jinge Bao, Aleksandrs Belovs, Troy Lee, Miklos Santha
2023	J	`jnl`	Optimal Composition Theorem for Randomized Query Complexity. Theory Comput. Dmytro Gavinsky, Troy Lee, Miklos Santha, Swagato Sanyal
2022	A*	`conf`	Cut Query Algorithms with Star Contraction. FOCS Simon Apers, Yuval Efron, Pawel Gawrychowski, Troy Lee, Sagnik Mukhopadhyay, Danupon Nanongkai
2022	J	`jnl`	Cut query algorithms with star contraction. CoRR Simon Apers, Yuval Efron, Pawel Gawrychowski, Troy Lee, Sagnik Mukhopadhyay, Danupon Nanongkai
2022	A	`conf`	Finding the KT Partition of a Weighted Graph in Near-Linear Time. APPROX/RANDOM Simon Apers, Pawel Gawrychowski, Troy Lee
2022	—	`book`	Query Complexity Mario Szegedy, Ilan Newman, Troy Lee
2021	J	`jnl`	A sublinear time quantum algorithm for s-t minimum cut on dense simple graphs. CoRR Simon Apers, Arinta Auza, Troy Lee
2021	J	`jnl`	Finding the KT partition of a weighted graph in near-linear time. CoRR Simon Apers, Pawel Gawrychowski, Troy Lee
2021	A	`conf`	On the Cut Dimension of a Graph. CCC Troy Lee, Tongyang Li, Miklos Santha, Shengyu Zhang
2021	J	`jnl`	On the query complexity of connectivity with global queries. CoRR Arinta Auza, Troy Lee
2021	A	`conf`	Quantum Complexity of Minimum Cut. CCC Simon Apers, Troy Lee
2021	A*	`conf`	Quantum algorithms for graph problems with cut queries. SODA Troy Lee, Miklos Santha, Shengyu Zhang
2021	J	`jnl`	Two new results about quantum exact learning. Quantum Srinivasan Arunachalam, Sourav Chakraborty, Troy Lee, Manaswi Paraashar, Ronald de Wolf
2020	J	`jnl`	On the cut dimension of a graph. CoRR Troy Lee, Tongyang Li, Miklos Santha, Shengyu Zhang
2020	J	`jnl`	Quadratically Tight Relations for Randomized Query Complexity. Theory Comput. Syst. Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs
2020	J	`jnl`	Quantum algorithms for graph problems with cut queries. CoRR Troy Lee, Miklos Santha, Shengyu Zhang
2020	J	`jnl`	Quantum query complexity of edge connectivity. CoRR Simon Apers, Troy Lee
2020	J	`jnl`	The quantum query complexity of composition with a relation. CoRR Aleksandrs Belovs, Troy Lee
2019	A*	`conf`	A Composition Theorem for Randomized Query Complexity via Max-Conflict Complexity. ICALP Dmitry Gavinsky, Troy Lee, Miklos Santha, Swagato Sanyal
2019	A	`conf`	Bounding Quantum-Classical Separations for Classes of Nonlocal Games. STACS Tom Bannink, Jop Briët, Harry Buhrman, Farrokh Labib, Troy Lee
2019	A	`conf`	Strategies for Quantum Races. ITCS Troy Lee, Maharshi Ray, Miklos Santha
2019	A*	`conf`	Two New Results About Quantum Exact Learning. ICALP Srinivasan Arunachalam, Sourav Chakraborty, Troy Lee, Manaswi Paraashar, Ronald de Wolf
2018	J	`jnl`	A composition theorem for randomized query complexity via max conflict complexity. CoRR Dmitry Gavinsky, Troy Lee, Miklos Santha, Swagato Sanyal
2018	J	`jnl`	On the randomised query complexity of composition. CoRR Dmitry Gavinsky, Troy Lee, Miklos Santha
2018	Misc	`conf`	Quadratically Tight Relations for Randomized Query Complexity. CSR Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs
2018	J	`jnl`	Quantum Attacks on Bitcoin, and How to Protect Against Them. Ledger Divesh Aggarwal, Gavin K. Brennen, Troy Lee, Miklos Santha, Marco Tomamichel
2018	J	`jnl`	Strategies for quantum races. CoRR Troy Lee, Maharshi Ray, Miklos Santha
2018	J	`jnl`	Two new results about quantum exact learning. CoRR Srinivasan Arunachalam, Sourav Chakraborty, Troy Lee, Ronald de Wolf
2017	—	`conf`	A Composition Theorem for Randomized Query Complexity. FSTTCS Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal
2017	J	`jnl`	A Composition Theorem for Randomized Query Complexity. CoRR Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal
2017	J	`jnl`	A Composition Theorem for Randomized Query complexity. Electron. Colloquium Comput. Complex. Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal
2017	J	`jnl`	Improved Quantum Query Algorithms for Triangle Detection and Associativity Testing. Algorithmica Troy Lee, Frédéric Magniez, Miklos Santha
2017	J	`jnl`	Information-theoretic approximations of the nonnegative rank. Comput. Complex. Gábor Braun, Rahul Jain, Troy Lee, Sebastian Pokutta
2017	J	`jnl`	Quadratically Tight Relations for Randomized Query Complexity. CoRR Dmitry Gavinsky, Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs
2017	J	`jnl`	Quadratically Tight Relations for Randomized Query Complexity. Electron. Colloquium Comput. Complex. Dmitry Gavinsky, Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs
2017	A	`conf`	Separating Quantum Communication and Approximate Rank. CCC Anurag Anshu, Shalev Ben-David, Ankit Garg, Rahul Jain, Robin Kothari, Troy Lee
2017	J	`jnl`	Separations in Query Complexity Based on Pointer Functions. J. ACM Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs
2017	J	`jnl`	Some upper and lower bounds on PSD-rank. Math. Program. Troy Lee, Zhaohui Wei, Ronald de Wolf
2016	J	`jnl`	Hellinger volume and number-on-the-forehead communication complexity. J. Comput. Syst. Sci. Troy Lee, Nikos Leonardos, Michael E. Saks, Fengming Wang
2016	A	`conf`	On the Sum-of-Squares Degree of Symmetric Quadratic Functions. CCC Troy Lee, Anupam Prakash, Ronald de Wolf, Henry Yuen
2016	J	`jnl`	On the sum-of-squares degree of symmetric quadratic functions. CoRR Troy Lee, Anupam Prakash, Ronald de Wolf, Henry Yuen
2016	J	`jnl`	Separating quantum communication and approximate rank. CoRR Anurag Anshu, Shalev Ben-David, Ankit Garg, Rahul Jain, Robin Kothari, Troy Lee
2016	A*	`conf`	Separations in Communication Complexity Using Cheat Sheets and Information Complexity. FOCS Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha
2016	J	`jnl`	Separations in communication complexity using cheat sheets and information complexity. CoRR Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha
2016	J	`jnl`	Separations in communication complexity using cheat sheets and information complexity. Electron. Colloquium Comput. Complex. Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha
2016	A*	`conf`	Separations in query complexity based on pointer functions. STOC Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs
2015	J	`jnl`	Fooling-sets and rank. Eur. J. Comb. Mirjam Friesen, Aya Hamed, Troy Lee, Dirk Oliver Theis
2015	J	`jnl`	Limitations of convex programming: lower bounds on extended formulations and factorization ranks (Dagstuhl Seminar 15082). Dagstuhl Reports Hartmut Klauck, Troy Lee, Dirk Oliver Theis, Rekha R. Thomas
2015	—	`conf`	Query Complexity in Expectation. ICALP (1) Jedrzej Kaniewski, Troy Lee, Ronald de Wolf
2015	J	`jnl`	Separations in Query Complexity Based on Pointer Functions. CoRR Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs
2015	J	`jnl`	Separations in Query Complexity Based on Pointer Functions. Electron. Colloquium Comput. Complex. Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs
2014	J	`jnl`	A quadratically tight partition bound for classical communication complexity and query complexity. CoRR Rahul Jain, Troy Lee, Nisheeth K. Vishnoi
2014	J	`jnl`	Hellinger volume and number-on-the-forehead communication complexity. CoRR Troy Lee, Nikos Leonardos, Michael E. Saks, Fengming Wang
2014	J	`jnl`	Query complexity in expectation. CoRR Jedrzej Kaniewski, Troy Lee, Ronald de Wolf
2014	J	`jnl`	Some upper and lower bounds on PSD-rank. CoRR Troy Lee, Zhaohui Wei, Ronald de Wolf
2014	—	`conf`	The Cover Number of a Matrix and its Algorithmic Applications. APPROX-RANDOM Noga Alon, Troy Lee, Adi Shraibman
2014	J	`jnl`	The square root rank of the correlation polytope is exponential. CoRR Troy Lee, Zhaohui Wei
2013	J	`jnl`	A strong direct product theorem for quantum query complexity. Comput. Complex. Troy Lee, Jérémie Roland
2013	J	`jnl`	Communication Complexity, Linear Optimization, and lower bounds for the nonnegative rank of matrices (Dagstuhl Seminar 13082). Dagstuhl Reports LeRoy B. Beasley, Hartmut Klauck, Troy Lee, Dirk Oliver Theis
2013	J	`jnl`	Dagstuhl Report 13082: Communication Complexity, Linear Optimization, and lower bounds for the nonnegative rank of matrices CoRR LeRoy Beasely, Troy Lee, Hartmut Klauck, Dirk Oliver Theis
2013	A*	`conf`	Improved quantum query algorithms for triangle finding and associativity testing. SODA Troy Lee, Frédéric Magniez, Miklos Santha
2013	J	`jnl`	Information-theoretic approximations of the nonnegative rank. Electron. Colloquium Comput. Complex. Gábor Braun, Rahul Jain, Troy Lee, Sebastian Pokutta
2013	—	`conf`	Matrix Completion From any Given Set of Observations. NIPS Troy Lee, Adi Shraibman
2013	J	`jnl`	Multipartite entanglement in XOR games. Quantum Inf. Comput. Jop Briët, Harry Buhrman, Troy Lee, Thomas Vidick
2013	J	`jnl`	Rank and fooling set size. CoRR Aya Hamed, Troy Lee
2013	A*	`conf`	The approximate rank of a matrix and its algorithmic applications: approximate rank. STOC Noga Alon, Troy Lee, Adi Shraibman, Santosh S. Vempala
2012	A	`conf`	A Strong Direct Product Theorem for Quantum Query Complexity. CCC Troy Lee, Jérémie Roland
2012	J	`jnl`	Learning graph based quantum query algorithms for finding constant-size subgraphs. Chic. J. Theor. Comput. Sci. Troy Lee, Frédéric Magniez, Miklos Santha
2012	C	`conf`	Lower Bounds for Sizes of Semidefinite Formulations for Some Combinatorial Optimization Problems. CTW Troy Lee, Dirk Oliver Theis
2012	J	`jnl`	Lower bounds for sizes of semidefinite formulations for some combinatorial optimization problems CoRR Troy Lee, Dirk Oliver Theis
2012	J	`jnl`	New bounds on the classical and quantum communication complexity of some graph properties CoRR Gábor Ivanyos, Hartmut Klauck, Troy Lee, Miklos Santha, Ronald de Wolf
2012	—	`conf`	New bounds on the classical and quantum communication complexity of some graph properties. FSTTCS Gábor Ivanyos, Hartmut Klauck, Troy Lee, Miklos Santha, Ronald de Wolf
2011	J	`jnl`	A learning graph based quantum query algorithm for finding constant-size subgraphs CoRR Troy Lee, Frédéric Magniez, Miklos Santha
2011	J	`jnl`	A strong direct product theorem for quantum query complexity CoRR Troy Lee, Jérémie Roland
2011	A*	`conf`	Quantum Query Complexity of State Conversion. FOCS Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Spalek, Mario Szegedy
2010	—	`conf`	Composition Theorems in Communication Complexity. ICALP (1) Troy Lee, Shengyu Zhang
2010	J	`jnl`	Composition theorems in communication complexity CoRR Troy Lee, Shengyu Zhang
2009	J	`jnl`	A note on the sign degree of formulas CoRR Troy Lee
2009	A	`conf`	An Approximation Algorithm for Approximation Rank. CCC Troy Lee, Adi Shraibman
2009	J	`jnl`	Disjointness is Hard in the Multiparty Number-on-the-Forehead Model. Comput. Complex. Troy Lee, Adi Shraibman
2009	J	`jnl`	Lower Bounds in Communication Complexity. Found. Trends Theor. Comput. Sci. Troy Lee, Adi Shraibman
2009	A	`conf`	Lower Bounds on Quantum Multiparty Communication Complexity. CCC Troy Lee, Gideon Schechtman, Adi Shraibman
2008	A	`conf`	A Direct Product Theorem for Discrepancy. CCC Troy Lee, Adi Shraibman, Robert Spalek
2008	J	`jnl`	An approximation algorithm for approximation rank CoRR Troy Lee, Adi Shraibman
2008	—	`conf`	Approximation norms and duality for communication complexity lower bounds. Computational Complexity of Discrete Problems Troy Lee, Adi Shraibman
2008	A	`conf`	Disjointness Is Hard in the Multi-party Number-on-the-Forehead Model. CCC Troy Lee, Adi Shraibman
2008	J	`jnl`	Disjointness is hard in the multi-party number-on-the-forehead model. Electron. Colloquium Comput. Complex. Troy Lee, Adi Shraibman
2008	—	`conf`	Optimal Quantum Adversary Lower Bounds for Ordered Search. ICALP (1) Andrew M. Childs, Troy Lee
2008	—	`conf`	Product Theorems Via Semidefinite Programming. ICALP (1) Troy Lee, Rajat Mittal
2008	J	`jnl`	Product theorems via semidefinite programming CoRR Troy Lee, Rajat Mittal
2007	A	`conf`	A New Rank Technique for Formula Size Lower Bounds. STACS Troy Lee
2007	J	`jnl`	Disjointness is hard in the multi-party number on the forehead model CoRR Troy Lee, Adi Shraibman
2007	A*	`conf`	Negative weights make adversaries stronger. STOC Peter Høyer, Troy Lee, Robert Spalek
2006	A	`conf`	Kolmogorov Complexity with Error. STACS Lance Fortnow, Troy Lee, Nikolai K. Vereshchagin
2006	J	`jnl`	The Quantum Adversary Method and Classical Formula Size Lower Bounds. Comput. Complex. Sophie Laplante, Troy Lee, Mario Szegedy
2005	J	`jnl`	Language compression and pseudorandom generators. Comput. Complex. Harry Buhrman, Troy Lee, Dieter van Melkebeek
2005	J	`jnl`	Resource bounded symmetry of information revisited. Theor. Comput. Sci. Troy Lee, Andrei Romashchenko
2005	A	`conf`	The Quantum Adversary Method and Classical Formula Size Lower Bounds. CCC Sophie Laplante, Troy Lee, Mario Szegedy
2004	J	`jnl`	Kolmogorov Complexity with Error Electron. Colloquium Comput. Complex. Lance Fortnow, Troy Lee, Nikolai K. Vereshchagin
2004	J	`jnl`	Language Compression and Pseudorandom Generators Electron. Colloquium Comput. Complex. Troy Lee, Dieter van Melkebeek, Harry Buhrman
2004	A	`conf`	Language Compression and Pseudorandom Generators. CCC Harry Buhrman, Troy Lee, Dieter van Melkebeek
2004	J	`jnl`	On Polynomially Time Bounded Symmetry of Information Electron. Colloquium Comput. Complex. Troy Lee, Andrei Romashchenko
2004	B	`conf`	On Polynomially Time Bounded Symmetry of Information. MFCS Troy Lee, Andrei Romashchenko
2003	J	`jnl`	Arithmetical definability over finite structures. Math. Log. Q. Troy Lee
2002	J	`jnl`	How Information-Mapping Patterns Determine Foraging Behaviour of a Honey Bee Colony. Open Syst. Inf. Dyn. Valery Tereshko, Troy Lee