default search action
Troy Lee
Person information
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2023
- [j20]Dmytro Gavinsky, Troy Lee, Miklos Santha, Swagato Sanyal:
Optimal Composition Theorem for Randomized Query Complexity. Theory Comput. 19: 1-35 (2023) - [i47]Jonathan Allcock, Jinge Bao, Aleksandrs Belovs, Troy Lee, Miklos Santha:
On the quantum time complexity of divide and conquer. CoRR abs/2311.16401 (2023) - 2022
- [b1]Mario Szegedy, Ilan Newman, Troy Lee:
Query Complexity. WorldScientific 2022, ISBN 9789813223202, pp. 1-200 - [c37]Simon Apers, Pawel Gawrychowski, Troy Lee:
Finding the KT Partition of a Weighted Graph in Near-Linear Time. APPROX/RANDOM 2022: 32:1-32:14 - [c36]Simon Apers, Yuval Efron, Pawel Gawrychowski, Troy Lee, Sagnik Mukhopadhyay
, Danupon Nanongkai:
Cut Query Algorithms with Star Contraction. FOCS 2022: 507-518 - [i46]Simon Apers, Yuval Efron, Pawel Gawrychowski, Troy Lee, Sagnik Mukhopadhyay, Danupon Nanongkai:
Cut query algorithms with star contraction. CoRR abs/2201.05674 (2022) - 2021
- [j19]Srinivasan Arunachalam, Sourav Chakraborty, Troy Lee, Manaswi Paraashar
Two new results about quantum exact learning. Quantum 5: 587 (2021) - [c35]Troy Lee, Tongyang Li
On the Cut Dimension of a Graph. CCC 2021: 15:1-15:35 - [c34]Simon Apers, Troy Lee:
Quantum Complexity of Minimum Cut. CCC 2021: 28:1-28:33 - [c33]Troy Lee, Miklos Santha, Shengyu Zhang:
Quantum algorithms for graph problems with cut queries. SODA 2021: 939-958 - [i45]Arinta Auza, Troy Lee:
On the query complexity of connectivity with global queries. CoRR abs/2109.02115 (2021) - [i44]Simon Apers, Arinta Auza, Troy Lee:
A sublinear time quantum algorithm for s-t minimum cut on dense simple graphs. CoRR abs/2110.15587 (2021) - [i43]Simon Apers, Pawel Gawrychowski, Troy Lee:
Finding the KT partition of a weighted graph in near-linear time. CoRR abs/2111.01378 (2021) - 2020
- [j18]Rahul Jain
Quadratically Tight Relations for Randomized Query Complexity. Theory Comput. Syst. 64(1): 101-119 (2020) - [i42]Aleksandrs Belovs, Troy Lee:
The quantum query complexity of composition with a relation. CoRR abs/2004.06439 (2020) - [i41]Troy Lee, Miklos Santha, Shengyu Zhang:
Quantum algorithms for graph problems with cut queries. CoRR abs/2007.08285 (2020) - [i40]Troy Lee, Tongyang Li, Miklos Santha, Shengyu Zhang:
On the cut dimension of a graph. CoRR abs/2011.05085 (2020) - [i39]Simon Apers, Troy Lee:
Quantum query complexity of edge connectivity. CoRR abs/2011.09823 (2020)
2010 – 2019
- 2019
- [c32]Srinivasan Arunachalam, Sourav Chakraborty, Troy Lee, Manaswi Paraashar
Two New Results About Quantum Exact Learning. ICALP 2019: 16:1-16:15 - [c31]Dmitry Gavinsky, Troy Lee, Miklos Santha, Swagato Sanyal:
A Composition Theorem for Randomized Query Complexity via Max-Conflict Complexity. ICALP 2019: 64:1-64:13 - [c30]Troy Lee, Maharshi Ray, Miklos Santha:
Strategies for Quantum Races. ITCS 2019: 51:1-51:21 - [c29]Tom Bannink, Jop Briët, Harry Buhrman, Farrokh Labib, Troy Lee:
Bounding Quantum-Classical Separations for Classes of Nonlocal Games. STACS 2019: 12:1-12:11 - 2018
- [j17]Divesh Aggarwal, Gavin K. Brennen
Quantum Attacks on Bitcoin, and How to Protect Against Them. Ledger 3 (2018) - [c28]Rahul Jain
Quadratically Tight Relations for Randomized Query Complexity. CSR 2018: 207-219 - [i38]Dmitry Gavinsky, Troy Lee, Miklos Santha:
On the randomised query complexity of composition. CoRR abs/1801.02226 (2018) - [i37]Troy Lee, Maharshi Ray, Miklos Santha:
Strategies for quantum races. CoRR abs/1809.03671 (2018) - [i36]Srinivasan Arunachalam, Sourav Chakraborty, Troy Lee, Ronald de Wolf:
Two new results about quantum exact learning. CoRR abs/1810.00481 (2018) - [i35]Dmitry Gavinsky, Troy Lee, Miklos Santha, Swagato Sanyal:
A composition theorem for randomized query complexity via max conflict complexity. CoRR abs/1811.10752 (2018) - 2017
- [j16]Troy Lee, Frédéric Magniez
Improved Quantum Query Algorithms for Triangle Detection and Associativity Testing. Algorithmica 77(2): 459-486 (2017) - [j15]Gábor Braun, Rahul Jain
Information-theoretic approximations of the nonnegative rank. Comput. Complex. 26(1): 147-197 (2017) - [j14]Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee
Separations in Query Complexity Based on Pointer Functions. J. ACM 64(5): 32:1-32:24 (2017) - [j13]Troy Lee, Zhaohui Wei
Some upper and lower bounds on PSD-rank. Math. Program. 162(1-2): 495-521 (2017) - [c27]Anurag Anshu, Shalev Ben-David, Ankit Garg, Rahul Jain
Separating Quantum Communication and Approximate Rank. CCC 2017: 24:1-24:33 - [c26]Anurag Anshu, Dmitry Gavinsky, Rahul Jain
A Composition Theorem for Randomized Query Complexity. FSTTCS 2017: 10:1-10:13 - [i34]Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal:
A Composition Theorem for Randomized Query Complexity. CoRR abs/1706.00335 (2017) - [i33]Dmitry Gavinsky, Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs:
Quadratically Tight Relations for Randomized Query Complexity. CoRR abs/1708.00822 (2017) - [i32]Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal:
A Composition Theorem for Randomized Query complexity. Electron. Colloquium Comput. Complex. TR17 (2017) - [i31]Dmitry Gavinsky, Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs:
Quadratically Tight Relations for Randomized Query Complexity. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [j12]Troy Lee, Nikos Leonardos, Michael E. Saks, Fengming Wang:
Hellinger volume and number-on-the-forehead communication complexity. J. Comput. Syst. Sci. 82(6): 1064-1074 (2016) - [c25]Troy Lee, Anupam Prakash, Ronald de Wolf, Henry Yuen:
On the Sum-of-Squares Degree of Symmetric Quadratic Functions. CCC 2016: 17:1-17:31 - [c24]Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain
Separations in Communication Complexity Using Cheat Sheets and Information Complexity. FOCS 2016: 555-564 - [c23]Andris Ambainis, Kaspars Balodis
Separations in query complexity based on pointer functions. STOC 2016: 800-813 - [i30]Troy Lee, Anupam Prakash, Ronald de Wolf, Henry Yuen:
On the sum-of-squares degree of symmetric quadratic functions. CoRR abs/1601.02311 (2016) - [i29]Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha:
Separations in communication complexity using cheat sheets and information complexity. CoRR abs/1605.01142 (2016) - [i28]Anurag Anshu, Shalev Ben-David, Ankit Garg, Rahul Jain, Robin Kothari, Troy Lee:
Separating quantum communication and approximate rank. CoRR abs/1611.05754 (2016) - [i27]Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha:
Separations in communication complexity using cheat sheets and information complexity. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [j11]Mirjam Friesen, Aya Hamed, Troy Lee, Dirk Oliver Theis:
Fooling-sets and rank. Eur. J. Comb. 48: 143-153 (2015) - [c22]Jedrzej Kaniewski
Query Complexity in Expectation. ICALP (1) 2015: 761-772 - [i26]Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs:
Separations in Query Complexity Based on Pointer Functions. CoRR abs/1506.04719 (2015) - [i25]Hartmut Klauck, Troy Lee, Dirk Oliver Theis, Rekha R. Thomas:
Limitations of convex programming: lower bounds on extended formulations and factorization ranks (Dagstuhl Seminar 15082). Dagstuhl Reports 5(2): 109-127 (2015) - [i24]Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs:
Separations in Query Complexity Based on Pointer Functions. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [c21]Noga Alon, Troy Lee, Adi Shraibman:
The Cover Number of a Matrix and its Algorithmic Applications. APPROX-RANDOM 2014: 34-47 - [i23]Rahul Jain, Troy Lee, Nisheeth K. Vishnoi:
A quadratically tight partition bound for classical communication complexity and query complexity. CoRR abs/1401.4512 (2014) - [i22]Troy Lee, Zhaohui Wei, Ronald de Wolf:
Some upper and lower bounds on PSD-rank. CoRR abs/1407.4308 (2014) - [i21]Troy Lee, Nikos Leonardos, Michael E. Saks, Fengming Wang:
Hellinger volume and number-on-the-forehead communication complexity. CoRR abs/1407.5425 (2014) - [i20]Troy Lee, Zhaohui Wei:
The square root rank of the correlation polytope is exponential. CoRR abs/1411.6712 (2014) - [i19]Jedrzej Kaniewski, Troy Lee, Ronald de Wolf:
Query complexity in expectation. CoRR abs/1411.7280 (2014) - 2013
- [j10]Troy Lee, Jérémie Roland
A strong direct product theorem for quantum query complexity. Comput. Complex. 22(2): 429-462 (2013) - [j9]Jop Briët, Harry Buhrman, Troy Lee, Thomas Vidick:
Multipartite entanglement in XOR games. Quantum Inf. Comput. 13(3-4): 334-360 (2013) - [c20]Troy Lee, Adi Shraibman:
Matrix Completion From any Given Set of Observations. NIPS 2013: 1781-1787 - [c19]Troy Lee, Frédéric Magniez, Miklos Santha:
Improved quantum query algorithms for triangle finding and associativity testing. SODA 2013: 1486-1502 - [c18]Noga Alon, Troy Lee, Adi Shraibman, Santosh S. Vempala:
The approximate rank of a matrix and its algorithmic applications: approximate rank. STOC 2013: 675-684 - [i18]LeRoy Beasely, Troy Lee, Hartmut Klauck, Dirk Oliver Theis:
Dagstuhl Report 13082: Communication Complexity, Linear Optimization, and lower bounds for the nonnegative rank of matrices. CoRR abs/1305.4147 (2013) - [i17]Aya Hamed, Troy Lee:
Rank and fooling set size. CoRR abs/1310.7321 (2013) - [i16]LeRoy B. Beasley, Hartmut Klauck, Troy Lee, Dirk Oliver Theis:
Communication Complexity, Linear Optimization, and lower bounds for the nonnegative rank of matrices (Dagstuhl Seminar 13082). Dagstuhl Reports 3(2): 127-143 (2013) - [i15]Gábor Braun, Rahul Jain, Troy Lee, Sebastian Pokutta:
Information-theoretic approximations of the nonnegative rank. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [j8]Troy Lee, Frédéric Magniez, Miklos Santha:
Learning graph based quantum query algorithms for finding constant-size subgraphs. Chic. J. Theor. Comput. Sci. 2012 (2012) - [c17]Troy Lee, Jérémie Roland
A Strong Direct Product Theorem for Quantum Query Complexity. CCC 2012: 236-246 - [c16]Troy Lee, Dirk Oliver Theis:
Lower Bounds for Sizes of Semidefinite Formulations for Some Combinatorial Optimization Problems. CTW 2012: 176-180 - [c15]Gábor Ivanyos
New bounds on the classical and quantum communication complexity of some graph properties. FSTTCS 2012: 148-159 - [i14]Troy Lee, Dirk Oliver Theis:
Lower bounds for sizes of semidefinite formulations for some combinatorial optimization problems. CoRR abs/1203.3961 (2012) - [i13]Gábor Ivanyos, Hartmut Klauck, Troy Lee, Miklos Santha, Ronald de Wolf:
New bounds on the classical and quantum communication complexity of some graph properties. CoRR abs/1204.4596 (2012) - 2011
- [c14]Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Spalek, Mario Szegedy:
Quantum Query Complexity of State Conversion. FOCS 2011: 344-353 - [i12]Troy Lee, Jérémie Roland:
A strong direct product theorem for quantum query complexity. CoRR abs/1104.4468 (2011) - [i11]Troy Lee, Frédéric Magniez, Miklos Santha:
A learning graph based quantum query algorithm for finding constant-size subgraphs. CoRR abs/1109.5135 (2011) - 2010
- [c13]Troy Lee, Shengyu Zhang:
Composition Theorems in Communication Complexity. ICALP (1) 2010: 475-489 - [i10]Troy Lee, Shengyu Zhang:
Composition theorems in communication complexity. CoRR abs/1003.1443 (2010)
2000 – 2009
- 2009
- [j7]Troy Lee, Adi Shraibman:
Disjointness is Hard in the Multiparty Number-on-the-Forehead Model. Comput. Complex. 18(2): 309-336 (2009) - [j6]Troy Lee, Adi Shraibman:
Lower Bounds in Communication Complexity. Found. Trends Theor. Comput. Sci. 3(4): 263-398 (2009) - [c12]Troy Lee, Gideon Schechtman, Adi Shraibman:
Lower Bounds on Quantum Multiparty Communication Complexity. CCC 2009: 254-262 - [c11]Troy Lee, Adi Shraibman:
An Approximation Algorithm for Approximation Rank. CCC 2009: 351-357 - [i9]Troy Lee:
A note on the sign degree of formulas. CoRR abs/0909.4607 (2009) - 2008
- [c10]Troy Lee, Adi Shraibman, Robert Spalek:
A Direct Product Theorem for Discrepancy. CCC 2008: 71-80 - [c9]Troy Lee, Adi Shraibman:
Disjointness Is Hard in the Multi-party Number-on-the-Forehead Model. CCC 2008: 81-91 - [c8]Troy Lee, Rajat Mittal:
Product Theorems Via Semidefinite Programming. ICALP (1) 2008: 674-685 - [c7]Andrew M. Childs, Troy Lee:
Optimal Quantum Adversary Lower Bounds for Ordered Search. ICALP (1) 2008: 869-880 - [i8]Troy Lee, Adi Shraibman:
Approximation norms and duality for communication complexity lower bounds. Computational Complexity of Discrete Problems 2008 - [i7]Troy Lee, Rajat Mittal:
Product theorems via semidefinite programming. CoRR abs/0803.4206 (2008) - [i6]Troy Lee, Adi Shraibman:
An approximation algorithm for approximation rank. CoRR abs/0809.2093 (2008) - [i5]Troy Lee, Adi Shraibman:
Disjointness is hard in the multi-party number-on-the-forehead model. Electron. Colloquium Comput. Complex. TR08 (2008) - 2007
- [c6]Troy Lee:
A New Rank Technique for Formula Size Lower Bounds. STACS 2007: 145-156 - [c5]Peter Høyer
Negative weights make adversaries stronger. STOC 2007: 526-535 - [i4]Troy Lee, Adi Shraibman:
Disjointness is hard in the multi-party number on the forehead model. CoRR abs/0712.4279 (2007) - 2006
- [j5]Sophie Laplante, Troy Lee, Mario Szegedy:
The Quantum Adversary Method and Classical Formula Size Lower Bounds. Comput. Complex. 15(2): 163-196 (2006) - [c4]Lance Fortnow, Troy Lee, Nikolai K. Vereshchagin:
Kolmogorov Complexity with Error. STACS 2006: 137-148 - 2005
- [j4]Harry Buhrman, Troy Lee, Dieter van Melkebeek:
Language compression and pseudorandom generators. Comput. Complex. 14(3): 228-255 (2005) - [j3]Troy Lee, Andrei E. Romashchenko
Resource bounded symmetry of information revisited. Theor. Comput. Sci. 345(2-3): 386-405 (2005) - [c3]Sophie Laplante, Troy Lee, Mario Szegedy:
The Quantum Adversary Method and Classical Formula Size Lower Bounds. CCC 2005: 76-90 - 2004
- [c2]Harry Buhrman, Troy Lee, Dieter van Melkebeek:
Language Compression and Pseudorandom Generators. CCC 2004: 15-28 - [c1]Troy Lee, Andrei E. Romashchenko:
On Polynomially Time Bounded Symmetry of Information. MFCS 2004: 463-475 - [i3]Troy Lee, Dieter van Melkebeek, Harry Buhrman:
Language Compression and Pseudorandom Generators. Electron. Colloquium Comput. Complex. TR04 (2004) - [i2]Troy Lee, Andrei E. Romashchenko:
On Polynomially Time Bounded Symmetry of Information. Electron. Colloquium Comput. Complex. TR04 (2004) - [i1]Lance Fortnow, Troy Lee, Nikolai K. Vereshchagin:
Kolmogorov Complexity with Error. Electron. Colloquium Comput. Complex. TR04 (2004) - 2003
- [j2]Troy Lee:
Arithmetical definability over finite structures. Math. Log. Q. 49(4): 385-392 (2003) - 2002
- [j1]Valery Tereshko
How Information-Mapping Patterns Determine Foraging Behaviour of a Honey Bee Colony. Open Syst. Inf. Dyn. 9(2): 181-194 (2002)
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-12-12 20:56 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: