Publication | Date of Publication | Type |
---|
https://portal.mardi4nfdi.de/entity/Q6147331 | 2024-01-15 | Paper |
Matrix discrepancy from Quantum communication | 2023-12-08 | Paper |
https://portal.mardi4nfdi.de/entity/Q5009564 | 2021-08-04 | Paper |
Approximating Rectangles by Juntas and Weakly Exponential Lower Bounds for LP Relaxations of CSPs | 2021-06-22 | Paper |
List Decodable Learning via Sum of Squares | 2021-02-02 | Paper |
Extended Formulation Lower Bounds for Refuting Random CSPs | 2021-02-02 | Paper |
Algorithms for heavy-tailed statistics: regression, covariance estimation, and beyond | 2021-01-19 | Paper |
Lifting sum-of-squares lower bounds: degree-2 to degree-4 | 2021-01-19 | Paper |
Dimension Reduction for Polynomials over Gaussian Space and Applications | 2020-09-22 | Paper |
HIGH DIMENSIONAL ESTIMATION VIA SUM-OF-SQUARES PROOFS | 2020-09-22 | Paper |
https://portal.mardi4nfdi.de/entity/Q5111409 | 2020-05-27 | Paper |
https://portal.mardi4nfdi.de/entity/Q5111411 | 2020-05-27 | Paper |
Algorithms for Heavy-Tailed Statistics: Regression, Covariance Estimation, and Beyond | 2019-12-23 | Paper |
Exponential Lower Bounds on Spectrahedral Representations of Hyperbolicity Cones | 2019-10-15 | Paper |
https://portal.mardi4nfdi.de/entity/Q5743406 | 2019-05-10 | Paper |
https://portal.mardi4nfdi.de/entity/Q5743431 | 2019-05-10 | Paper |
https://portal.mardi4nfdi.de/entity/Q5743465 | 2019-05-10 | Paper |
https://portal.mardi4nfdi.de/entity/Q4633863 | 2019-05-06 | Paper |
On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique | 2018-11-13 | Paper |
Bypassing UGC from Some Optimal Geometric Inapproximability Results | 2018-10-30 | Paper |
Approximate Constraint Satisfaction Requires Large LP Relaxations | 2018-08-02 | Paper |
The matching problem has no small symmetric SDP | 2018-07-16 | Paper |
On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique | 2018-07-16 | Paper |
https://portal.mardi4nfdi.de/entity/Q4638054 | 2018-05-03 | Paper |
https://portal.mardi4nfdi.de/entity/Q4598219 | 2017-12-19 | Paper |
The matching problem has no small symmetric SDP | 2017-10-27 | Paper |
Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs | 2017-08-17 | Paper |
https://portal.mardi4nfdi.de/entity/Q2969633 | 2017-03-22 | Paper |
Making the Long Code Shorter | 2015-11-04 | Paper |
Hardness of Solving Sparse Overdetermined Linear Systems | 2015-09-24 | Paper |
Lower Bounds on the Size of Semidefinite Programming Relaxations | 2015-08-21 | Paper |
List Decoding Tensor Products and Interleaved Codes | 2015-02-04 | Paper |
Bounding the average sensitivity and noise sensitivity of polynomial threshold functions | 2014-08-13 | Paper |
Approximations for the isoperimetric and spectral profile of graphs and related parameters | 2014-08-13 | Paper |
Graph expansion and the unique games conjecture | 2014-08-13 | Paper |
Rounding Semidefinite Programming Hierarchies via Global Correlation | 2014-07-30 | Paper |
Agnostic Learning of Monomials by Halfspaces Is Hard | 2014-07-25 | Paper |
Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES | 2014-07-25 | Paper |
How to Round Any CSP | 2014-07-25 | Paper |
Average Sensitivity and Noise Sensitivity of Polynomial Threshold Functions | 2014-06-04 | Paper |
Many sparse cuts via higher eigenvalues | 2014-05-13 | Paper |
On mimicking networks representing minimum terminal cuts | 2014-04-17 | Paper |
Improved approximation algorithms for the spanning star forest problem | 2013-08-05 | Paper |
Agnostic Learning of Monomials by Halfspaces Is Hard | 2013-03-19 | Paper |
Buffer management for colored packets with deadlines | 2012-12-10 | Paper |
Testing Odd-Cycle-Freeness in Boolean Functions | 2012-10-31 | Paper |
List Decoding Tensor Products and Interleaved Codes | 2012-02-11 | Paper |
Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant | 2011-10-18 | Paper |
Algorithmic Extensions of Cheeger’s Inequality to Higher Eigenvalues and Partitions | 2011-08-17 | Paper |
Approximating Sparsest Cut in Graphs of Bounded Treewidth | 2010-09-10 | Paper |
Hardness of Learning Halfspaces with Noise | 2010-04-29 | Paper |
Coarse differentiation and multi-flows in planar graphs | 2010-03-04 | Paper |
Perfectly reliable and secure message transmission tolerating mobile adversary | 2009-05-12 | Paper |
On Proactive Perfectly Secure Message Transmission | 2009-03-06 | Paper |
Improved Approximation Algorithms for the Spanning Star Forest Problem | 2009-02-17 | Paper |
Coarse Differentiation and Multi-flows in Planar Graphs | 2009-02-17 | Paper |
https://portal.mardi4nfdi.de/entity/Q3549614 | 2009-01-05 | Paper |
https://portal.mardi4nfdi.de/entity/Q3549676 | 2009-01-05 | Paper |
https://portal.mardi4nfdi.de/entity/Q3549708 | 2009-01-05 | Paper |
Constraint Satisfaction over a Non-Boolean Domain: Approximation Algorithms and Unique-Games Hardness | 2008-11-27 | Paper |