45 papers
cs cc
0/02024
12021
22020
5- NovOn the cut dimension of a graphno summary yetcs-cc2011.05085Tencent1 citesNov 10, 2020
- NovThe Strongish Planted Clique Hypothesis and Its Consequencesno summary yetcs-cc2011.05555Google Research0 citesNov 11, 2020
- JulComputational Complexity Characterization of Protecting Elections from Briberyno summary yetcs-cc2007.02533Amazon0 citesJul 6, 2020
- JunWhen Is Amplification Necessary for Composition in Randomized Query Complexity?no summary yetcs-cc2006.10957Microsoft Research2 citesJun 19, 2020
- FebA Tight Composition Theorem for the Randomized Query Complexity of Partial Functionsno summary yetcs-cc2002.10809Microsoft Research6 citesFeb 25, 2020
2019
22018
3- SepSpanoids - an abstraction of spanning structures, and a barrier for LCCsno summary yetcs-cc1809.10372Microsoft Research0 citesSep 27, 2018
- AugAlgorithmic No-Cloning Theoremno summary yetcs-cc1808.04213Google Research0 citesAug 9, 2018
- MayQuantum generalizations of the polynomial hierarchy with applications to QMA(2)no summary yetcs-cc1805.11139Microsoft Research3 citesMay 28, 2018
2017
6- OctThe space complexity of mirror gamesno summary yetcs-cc1710.02898Google Research0 citesOct 8, 2017
- OctBarriers for Rank Methods in Arithmetic Complexityno summary yetcs-cc1710.09502Microsoft Research0 citesOct 26, 2017
- AugDimension Reduction for Polynomials over Gaussian Space and Applicationsno summary yetcs-cc1708.03808Google Research1 citesAug 12, 2017
- JunTree-Residue Vertex-Breaking: a new tool for proving hardnessno summary yetcs-cc1706.07900Google Research5 citesJun 24, 2017
- AprOptimal lower bounds for universal relation, and for samplers and finding duplicates in streamsno summary yetcs-cc1704.00633OpenAI4 citesApr 3, 2017
- FebA Converse to Banach's Fixed Point Theorem and its CLS Completenessno summary yetcs-cc1702.07339Microsoft Research1 citesFeb 23, 2017
2016
12015
4- AugSmooth Boolean functions are easy: efficient algorithms for low-sensitivity functionsno summary yetcs-cc1508.02420Microsoft Research2 citesAug 10, 2015
- MayBeating the random assignment on constraint satisfaction problems of bounded degreeno summary yetcs-cc1505.03424Microsoft Research27 citesMay 13, 2015
- MayComplexity Theoretic Limitations on Learning Halfspacesno summary yetcs-cc1505.05800Google Research5 citesMay 21, 2015
- JanSum of Squares Lower Bounds from Pairwise Independenceno summary yetcs-cc1501.00734Microsoft Research0 citesJan 4, 2015
2014
2- JunReductions to the set of random strings: The resource-bounded caseno summary yetcs-cc1406.7658Google Research6 citesJun 30, 2014
- MarMaximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-based Approximation Algorithmno summary yetcs-cc1403.7721Microsoft Research2 citesMar 30, 2014
2013
22012
12011
3- AprFairness Through Awarenessno summary yetcs-cc1104.3913Microsoft Research43 citesApr 20, 2011
- FebSpectral Algorithms for Unique Gamesno summary yetcs-cc1102.2300Microsoft Research0 citesFeb 11, 2011
- JanAlmost Settling the Hardness of Noncommutative Determinantno summary yetcs-cc1101.1169Google Research6 citesJan 6, 2011
2010
6- DecAgnostic Learning of Monomials by Halfspaces is Hardno summary yetcs-cc1012.0729Microsoft Research5 citesDec 3, 2010
- NovReductions Between Expansion Problemsno summary yetcs-cc1011.2586Microsoft Research5 citesNov 11, 2010
- NovStrong direct product theorems for quantum communication and query complexityno summary yetcs-cc1011.4935Microsoft Research3 citesNov 22, 2010
- MayOn Tractable Exponential Sumsno summary yetcs-cc1005.2632Microsoft Research15 citesMay 14, 2010
- MayComputational Transition at the Uniqueness Thresholdno summary yetcs-cc1005.5584Microsoft Research43 citesMay 31, 2010
- JanCollapsing and Separating Completeness Notions under Average-Case and Worst-Case Hypothesesno summary yetcs-cc1001.0117LinkedIn0 citesJan 4, 2010
2009
3- OctUsing Elimination Theory to construct Rigid Matricesno summary yetcs-cc0910.5301Microsoft Research12 citesOct 28, 2009
- AugApproximate Counting and Quantum Computationno summary yetcs-cc0908.2122Microsoft Research0 citesAug 14, 2009
- AprSettling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilitiesno summary yetcs-cc0904.0644Microsoft Research14 citesApr 3, 2009
2008
4- MarA Dual Polynomial for ORno summary yetcs-cc0803.4516Google Research24 citesMar 31, 2008
- Feb3-Way Composition of Weighted Finite-State Transducersno summary yetcs-cc0802.1465Google Research0 citesFeb 11, 2008
- FebGeneral Algorithms for Testing the Ambiguity of Finite Automatano summary yetcs-cc0802.3254Google Research0 citesFeb 22, 2008
- FebCurves That Must Be Retracedno summary yetcs-cc0802.4312LinkedIn1 citesFeb 29, 2008