| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Rocco A. Servedio, Li-Yang Tan |
Fooling Intersections of Low-Weight Halfspaces.  |
FOCS  |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart |
Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael Kapralov, Jelani Nelson, Jakub Pachocki, Zhengyu Wang, David P. Woodruff, Mobin Yahyazadeh |
Optimal Lower Bounds for Universal Relation, and for Samplers and Finding Duplicates in Streams. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Vincent Cohen-Addad, Chris Schwiegelshohn |
On the Local Structure of Stable Clustering Instances. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Brett Hemenway, Noga Ron-Zewi, Mary Wootters |
Local List Recovery of High-Rate Tensor Codes & Applications. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Nima Anari, Leonid Gurvits, Shayan Oveis Gharan, Amin Saberi |
Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael Kapralov |
Sample Efficient Estimation and Recovery in Sparse FFT via Isolation on Average. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Jingcheng Liu 0001, Alistair Sinclair, Piyush Srivastava 0001 |
The Ising Partition Function: Zeros and Deterministic Approximation. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | András Pal Gilyén, Or Sattath |
On Preparing Ground States of Gapped Hamiltonians: An Efficient Quantum Lovász Local Lemma. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark Braverman, Rotem Oshman |
A Rounds vs. Communication Tradeoff for Multi-Party Set Disjointness. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Yin Tat Lee, Santosh Srinivas Vempala |
Eldan's Stochastic Localization and the KLS Hyperplane Conjecture: An Improved Lower Bound for Expansion. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Yang Cai 0001, Constantinos Daskalakis |
Learning Multi-Item Auctions with (or without) Samples. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Glencora Borradaile, Hung Le 0001, Christian Wulff-Nilsen |
Minor-Free Graphs Have Light Spanners. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Amir Abboud, Aviad Rubinstein, R. Ryan Williams |
Distributed PCP Theorems for Hardness of Approximation in P. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Benny Applebaum |
Exponentially-Hard Gap-CSP and Local PRG via Local Hardcore Functions. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Danupon Nanongkai, Thatchaphol Saranurak, Christian Wulff-Nilsen |
Dynamic Minimum Spanning Forest with Subpolynomial Worst-Case Update Time. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Sanjam Garg, Akshayaram Srinivasan |
Garbled Protocols and Two-Round MPC from Bilinear Maps. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Ilan Komargodski, Moni Naor, Eylon Yogev |
White-Box vs. Black-Box Complexity of Search Problems: Ramsey and Graph Property Testing. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Pavel Hrubes, Pavel Pudlák |
Random Formulas, Monotone Circuits, and Interpolation. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Daniel Wichs, Giorgos Zirdelis |
Obfuscating Compute-and-Compare Programs under LWE. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark Bun, Justin Thaler |
A Nearly Optimal Lower Bound on the Approximate Degree of AC0. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | David Durfee, John Peebles, Richard Peng, Anup B. Rao |
Determinant-Preserving Sparsification of SDDM Matrices with Applications to Counting and Sampling Spanning Trees. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Waldo Gálvez, Fabrizio Grandoni 0001, Sandy Heydrich, Salvatore Ingala, Arindam Khan 0001, Andreas Wiese |
Approximating Geometric Knapsack via L-Packings. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Cameron Musco, David P. Woodruff |
Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Tugkan Batu, Clément L. Canonne |
Generalized Uniformity Testing. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani |
Weak Decoupling, Polynomial Folds and Approximate Optimization over the Sphere. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Yinan Li, Youming Qiao |
Linear Algebraic Analogues of the Graph Isomorphism Problem and the Erdős-Rényi Model. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Chris Umans (eds.) |
58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017 |
FOCS |
2017 |
DBLP BibTeX RDF |
|
| 1 | Danny Nguyen, Igor Pak |
Short Presburger Arithmetic Is Hard. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Oded Regev 0001, Aravindan Vijayaraghavan |
On Learning Mixtures of Well-Separated Gaussians. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Vincent Cohen-Addad, Søren Dahlgaard, Christian Wulff-Nilsen |
Fast and Compact Exact Distance Oracle for Planar Graphs. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Thomas Steinke 0002, Jonathan R. Ullman |
Tight Lower Bounds for Differentially Private Selection. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Nikhil Bansal 0001, Marek Eliás 0001, Grigorios Koumoutsos |
Weighted k-Server Bounds via Combinatorial Dichotomies. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Mika Göös, Toniann Pitassi, Thomas Watson 0001 |
Query-to-Communication Lifting for BPP. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Ola Svensson, Jakub Tarnawski |
The Matching Problem in General Graphs Is in Quasi-NC. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Rocco A. Servedio, Li-Yang Tan |
Deterministic Search for CNF Satisfying Assignments in Almost Polynomial Time. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Javad B. Ebrahimi, Damian Straszak, Nisheeth K. Vishnoi |
Subdeterminant Maximization via Nonconvex Relaxations and Anti-Concentration. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Fernando G. S. L. Brandão, Krysta M. Svore |
Quantum Speed-Ups for Solving Semidefinite Programs. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Chien-Chung Huang, Danupon Nanongkai, Thatchaphol Saranurak |
Distributed Exact Weighted All-Pairs Shortest Paths in Õ(n5/4) Rounds. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Shi Li 0001 |
Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Rasmus Kyng, Peng Zhang 0052 |
Hardness Results for Structured Linear Systems. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Mikkel Thorup |
Fast Similarity Sketching. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Kun He 0011, Liang Li, Xingwu Liu, Yuyi Wang 0001, Mingji Xia |
Variable-Version Lovász Local Lemma: Beyond Shearer's Bound. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Huck Bennett, Alexander Golovnev, Noah Stephens-Davidowitz |
On the Quantitative Hardness of CVP. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Felix Joos, Jaehoon Kim, Daniela Kühn, Deryk Osthus |
A Characterization of Testable Hypergraph Properties. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Yuval Peres, Alex Zhai |
Average-Case Reconstruction for the Deletion Channel: Subpolynomially Many Traces Suffice. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Adam Bouland, Lijie Chen 0001, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan |
On the Power of Statistical Zero Knowledge. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael B. Cohen, Aleksander Madry, Dimitris Tsipras, Adrian Vladu |
Matrix Scaling and Balancing via Box Constrained Newton's Method and Interior Point Methods. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Joran van Apeldoorn, András Gilyén, Sander Gribling, Ronald de Wolf |
Quantum SDP-Solvers: Better Upper and Lower Bounds. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Thomas Dybdahl Ahle |
Optimal Las Vegas Locality Sensitive Data Structures. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Noga Alon, Bo'az Klartag |
Optimal Compression of Approximate Inner Products and Dimension Reduction. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Miroslav Dudík, Nika Haghtalab, Haipeng Luo, Robert E. Schapire, Vasilis Syrgkanis, Jennifer Wortman Vaughan |
Oracle-Efficient Online Learning and Auction Design. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Ran Raz |
A Time-Space Lower Bound for a Large Class of Learning Problems. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Daniel Kane 0001, Sushrut Karmalkar, Eric Price 0001 |
Robust Polynomial Regression up to the Information Theoretic Limit. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Zeyuan Allen-Zhu, Yuanzhi Li |
First Efficient Convergence for Streaming k-PCA: A Global, Gap-Free, and Near-Optimal Rate. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Barna Saha |
Fast & Space-Efficient Approximations of Language Edit Distance and RNA Folding: An Amnesic Dynamic Programming Approach. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Lior Eldar, Aram W. Harrow |
Local Hamiltonians Whose Ground States Are Hard to Approximate. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann |
Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-and-Solve. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Håstad |
On Small-Depth Frege Proofs for Tseitin for Grids. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Alexander A. Sherstov, Pei Wu |
Optimal Interactive Coding for Insertions, Deletions, and Substitutions. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Samuel B. Hopkins, David Steurer |
Efficient Bayesian Estimation from Few Samples: Community Detection and Related Problems. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Kasper Green Larsen, Jelani Nelson |
Optimality of the Johnson-Lindenstrauss Lemma. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark de Berg |
Removing Depth-Order Cycles among Triangles: An Efficient Algorithm Generating Triangular Fragments. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Zeyuan Allen-Zhu, Yuanzhi Li, Rafael Mendes de Oliveira, Avi Wigderson |
Much Faster Algorithms for Matrix Scaling. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Itzhak Tamo, Min Ye 0005, Alexander Barg |
Optimal Repair of Reed-Solomon Codes: Achieving the Cut-Set Bound. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Noga Alon, Omri Ben-Eliezer, Eldar Fischer |
Testing Hereditary Properties of Ordered Graphs and Matrices. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Chandra Chekuri, Kent Quanrud |
Approximating the Held-Karp Bound for Metric TSP in Nearly-Linear Time. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Dmitriy Zhuk |
A Proof of CSP Dichotomy Conjecture. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, David Steurer |
The Power of Sum-of-Squares for Detecting Hidden Structures. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrei A. Bulatov |
A Dichotomy Theorem for Nonuniform CSPs. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Xi Chen 0001, Erik Waingarten, Jinyu Xie |
Boolean Unateness Testing with Õ(n3/4) Adaptive Queries. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Ken-ichi Kawarabayashi, Anastasios Sidiropoulos |
Polylogarithmic Approximation for Minimum Planarization (Almost). |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Leslie G. Valiant |
Capacity of Neural Networks for Lifelong Learning of Composable Tasks. |
FOCS |
2017 |
DBLP DOI BibTeX RDF |
|
| 1 | Gil Cohen, Leonard J. Schulman |
Extractors for Near Logarithmic Min-Entropy. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Anne Broadbent, Zhengfeng Ji, Fang Song 0001, John Watrous |
Zero-Knowledge Proof Systems for QMA. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Julia Chuzhoy, Alina Ene |
On Approximating Maximum Independent Set of Rectangles. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Huijia Lin, Vinod Vaikuntanathan |
Indistinguishability Obfuscation from DDH-Like Assumptions on Constant-Degree Graded Encodings. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Robert Robere, Toniann Pitassi, Benjamin Rossman, Stephen A. Cook |
Exponential Lower Bounds for Monotone Span Programs. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Venkata Gandikota, Badih Ghazi, Elena Grigorescu |
NP-Hardness of Reed-Solomon Decoding and the Prouhet-Tarry-Escott Problem. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Aviad Rubinstein |
Settling the Complexity of Computing Approximate Two-Player Nash Equilibria. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Alexander A. Sherstov |
Compressing Interactive Communication under Product Distributions. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Omri Weinstein, Huacheng Yu |
Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Vladimir Kolmogorov |
Commutativity in the Algorithmic Lovász Local Lemma. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Felix Joos, Guillem Perarnau, Dieter Rautenbach, Bruce A. Reed |
How to Determine if a Random Graph with a Fixed Degree Sequence Has a Giant Component. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Mika Göös, Rahul Jain 0001, Thomas Watson 0001 |
Extension Complexity of Independent Set Polytopes. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Elizabeth Crosson, Aram W. Harrow |
Simulated Quaotum Annealing Can Be Exponentially Faster Than Classical Simulated Annealing. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael B. Cohen |
Ramanujan Graphs in Polynomial Time. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Venkatesan Guruswami, David Zuckerman |
Robust Fourier and Polynomial Curve Fitting. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Ryan M. Rogers, Aaron Roth 0001, Adam D. Smith, Om Thakkar 0001 |
Max-Information, Differential Privacy, and Post-selection Hypothesis Testing. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Ofer Grossman, Dana Moshkovitz |
Amplification and Derandomization without Slowdown. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Ilias Diakonikolas, Gautam Kamath 0001, Daniel M. Kane, Jerry Li 0001, Ankur Moitra, Alistair Stewart |
Robust Estimators in High Dimensions without the Computational Intractability. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Haris Aziz 0001, Simon Mackenzie |
A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Johan Håstad |
An Average-Case Depth Hierarchy Theorem for Higher Depth. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie |
An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Hubie Chen, Matthew Valeriote, Yuichi Yoshida |
Testing Assignments to Constraint Satisfaction Problems. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Hamed Hatami, Kaave Hosseini, Shachar Lovett |
Structure of Protocols for XOR Functions. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Allan Sly, Nike Sun, Yumeng Zhang |
The Number of Solutions for Random Regular NAE-SAT. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Zohar S. Karnin, Kevin J. Lang, Edo Liberty |
Optimal Quantile Approximation in Streams. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Mathias Bæk Tejs Knudsen |
Linear Hashing Is Awesome. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Yossi Azar, Niv Buchbinder, T.-H. Hubert Chan, Shahar Chen, Ilan Reuven Cohen, Anupam Gupta 0001, Zhiyi Huang 0002, Ning Kang 0001, Viswanath Nagarajan, Joseph Naor, Debmalya Panigrahi |
Online Algorithms for Covering and Packing Problems with Convex Objectives. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")
data released under the ODC-BY 1.0 license