Google
Google Scholar
MS Academic
CiteSeerX
CORE
Semantic Scholar58th FOCS 2017: Berkeley, CA, USA
Chris Umans:
58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017. IEEE Computer Society 2017, ISBN 978-1-5386-3464-6
Session 1A
- Huck Bennett, Alexander Golovnev, Noah Stephens-Davidowitz:
On the Quantitative Hardness of CVP. 13-24 - Amir Abboud, Aviad Rubinstein, R. Ryan Williams:
Distributed PCP Theorems for Hardness of Approximation in P. 25-36
Session 1B
- Vincent Cohen-Addad, Chris Schwiegelshohn:
On the Local Structure of Stable Clustering Instances. 49-60 - Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, Justin Ward:
Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms. 61-72 - Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart:
Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures. 73-84
Session 2A
- Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere:
Random Θ(log n)-CNFs Are Hard for Cutting Planes. 109-120 - Mark Braverman, Rotem Oshman:
A Rounds vs. Communication Tradeoff for Multi-Party Set Disjointness. 144-155
Session 2B
- Chien-Chung Huang, Danupon Nanongkai, Thatchaphol Saranurak:
Distributed Exact Weighted All-Pairs Shortest Paths in Õ(n5/4) Rounds. 168-179 - Manuela Fischer, Mohsen Ghaffari, Fabian Kuhn:
Deterministic Distributed Edge-Coloring via Hypergraph Maximal Matching. 180-191 - Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann:
Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-and-Solve. 192-203
Session 3A
- Brett Hemenway, Noga Ron-Zewi, Mary Wootters:
Local List Recovery of High-Rate Tensor Codes & Applications. 204-215 - Itzhak Tamo, Min Ye, Alexander Barg:
Optimal Repair of Reed-Solomon Codes: Achieving the Cut-Set Bound. 216-227 - Yuval Peres, Alex Zhai:
Average-Case Reconstruction for the Deletion Channel: Subpolynomially Many Traces Suffice. 228-239 - Alexander A. Sherstov, Pei Wu:
Optimal Interactive Coding for Insertions, Deletions, and Substitutions. 240-251 - Daniel Kane, Shachar Lovett, Sankeerth Rao:
The Independence Number of the Birkhoff Polytope Graph, and Applications to Maximally Recoverable Codes. 252-259
Session 3B
- Waldo Gálvez, Fabrizio Grandoni, Sandy Heydrich, Salvatore Ingala, Arindam Khan, Andreas Wiese:
Approximating Geometric Knapsack via L-Packings. 260-271 - Mark de Berg:
Removing Depth-Order Cycles among Triangles: An Efficient Algorithm Generating Triangular Fragments. 272-282 - Shi Li:
Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations. 283-294 - Barna Saha:
Fast & Space-Efficient Approximations of Language Edit Distance and RNA Folding: An Amnesic Dynamic Programming Approach. 295-306 - Karl Bringmann, Allan Grønlund, Kasper Green Larsen:
A Dichotomy for Regular Expression Membership Testing. 307-318
Session 4
Session 5A
- Daniel M. Kane, Shachar Lovett, Shay Moran, Jiapeng Zhang:
Active Classification with Comparison Queries. 355-366 - Samuel B. Hopkins, David Steurer:
Efficient Bayesian Estimation from Few Samples: Community Detection and Related Problems. 379-390 - Daniel Kane, Sushrut Karmalkar, Eric Price:
Robust Polynomial Regression up to the Information Theoretic Limit. 391-402
Session 5B
- Joran van Apeldoorn, András Gilyén, Sander Gribling, Ronald de Wolf:
Quantum SDP-Solvers: Better Upper and Lower Bounds. 403-414 - Fernando G. S. L. Brandão, Krysta M. Svore:
Quantum Speed-Ups for Solving Semidefinite Programs. 415-426 - Lior Eldar, Aram Wettroth Harrow:
Local Hamiltonians Whose Ground States Are Hard to Approximate. 427-438 - András Pal Gilyén, Or Sattath:
On Preparing Ground States of Gapped Hamiltonians: An Efficient Quantum Lovász Local Lemma. 439-450 - Kun He, Liang Li, Xingwu Liu, Yuyi Wang, Mingji Xia:
Variable-Version Lovász Local Lemma: Beyond Shearer's Bound. 451-462 - Yinan Li, Youming Qiao:
Linear Algebraic Analogues of the Graph Isomorphism Problem and the Erdős-Rényi Model. 463-474
Session 6A
- 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. 475-486 - Zeyuan Allen-Zhu, Yuanzhi Li:
First Efficient Convergence for Streaming k-PCA: A Global, Gap-Free, and Near-Optimal Rate. 487-492 - Nikhil Bansal, Marek Eliás, Grigorios Koumoutsos:
Weighted k-Server Bounds via Combinatorial Dichotomies. 493-504 - Krati Nayyar, Sharath Raghvendra:
An Input Sensitive Online Algorithm for the Metric Bipartite Matching Problem. 505-515
Session 6B
- Miroslav Dudík, Nika Haghtalab, Haipeng Luo, Robert E. Schapire, Vasilis Syrgkanis, Jennifer Wortman Vaughan:
Oracle-Efficient Online Learning and Auction Design. 528-539 - Paul Duetting, Michal Feldman, Thomas Kesselheim, Brendan Lucier:
Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Non-Stochastic Inputs. 540-551
Session 7A
- Huijia Lin, Rafael Pass, Pratik Soni:
Two-Round and Non-Interactive Concurrent Non-Malleable Commitments from Time-Lock Puzzles. 576-587 - Ilan Komargodski, Moni Naor, Eylon Yogev:
White-Box vs. Black-Box Complexity of Search Problems: Ramsey and Graph Property Testing. 622-632
Session 7B
- Noga Alon, Bo'az Klartag:
Optimal Compression of Approximate Inner Products and Dimension Reduction. 639-650 - Michael Kapralov:
Sample Efficient Estimation and Recovery in Sparse FFT via Isolation on Average. 651-662 - Cameron Musco, David P. Woodruff:
Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices. 672-683
Session 8
Session 9A
- Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan:
On the Power of Statistical Zero Knowledge. 708-719 - Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, David Steurer:
The Power of Sum-of-Squares for Detecting Hidden Structures. 720-731 - Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan:
From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More. 743-754
Session 9B
- David R. Karger:
Faster (and Still Pretty Simple) Unbiased Estimators for Network (Un)reliability. 755-766 - Glencora Borradaile, Hung Le, Christian Wulff-Nilsen:
Minor-Free Graphs Have Light Spanners. 767-778 - Ken-ichi Kawarabayashi, Anastasios Sidiropoulos:
Polylogarithmic Approximation for Minimum Planarization (Almost). 779-788 - Chandra Chekuri, Kent Quanrud:
Approximating the Held-Karp Bound for Metric TSP in Nearly-Linear Time. 789-800
Session 10A
- Jack Murtagh, Omer Reingold, Aaron Sidford, Salil P. Vadhan:
Derandomization Beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space. 801-812 - Rocco A. Servedio, Li-Yang Tan:
Deterministic Search for CNF Satisfying Assignments in Almost Polynomial Time. 813-823
Session 10B
- Noga Alon, Omri Ben-Eliezer, Eldar Fischer:
Testing Hereditary Properties of Ordered Graphs and Matrices. 848-858 - Felix Joos, Jaehoon Kim, Daniela Kühn, Deryk Osthus:
A Characterization of Testable Hypergraph Properties. 859-867 - Xi Chen, Erik Waingarten, Jinyu Xie:
Boolean Unateness Testing with Õ(n3/4) Adaptive Queries. 868-879
Session 11A
- Zeyuan Allen-Zhu, Yuanzhi Li, Rafael Mendes de Oliveira, Avi Wigderson:
Much Faster Algorithms for Matrix Scaling. 890-901 - Michael B. Cohen, Aleksander Madry, Dimitris Tsipras, Adrian Vladu:
Matrix Scaling and Balancing via Box Constrained Newton's Method and Interior Point Methods. 902-913 - Nima Anari, Leonid Gurvits, Shayan Oveis Gharan, Amin Saberi:
Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices. 914-925 - David Durfee, John Peebles, Richard Peng, Anup B. Rao:
Determinant-Preserving Sparsification of SDDM Matrices with Applications to Counting and Sampling Spanning Trees. 926-937
Session 11B
- Danupon Nanongkai, Thatchaphol Saranurak, Christian Wulff-Nilsen:
Dynamic Minimum Spanning Forest with Subpolynomial Worst-Case Update Time. 950-961 - Vincent Cohen-Addad, Søren Dahlgaard, Christian Wulff-Nilsen:
Fast and Compact Exact Distance Oracle for Planar Graphs. 962-973
Session 12A
- Jingcheng Liu, Alistair Sinclair, Piyush Srivastava:
The Ising Partition Function: Zeros and Deterministic Approximation. 986-997 - Yin Tat Lee, Santosh Srinivas Vempala:
Eldan's Stochastic Localization and the KLS Hyperplane Conjecture: An Improved Lower Bound for Expansion. 998-1007
Session 12B
- Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani:
Weak Decoupling, Polynomial Folds and Approximate Optimization over the Sphere. 1008-1019 - Javad B. Ebrahimi, Damian Straszak, Nisheeth K. Vishnoi:
Subdeterminant Maximization via Nonconvex Relaxations and Anti-Concentration. 1020-1031 - Moses Charikar, Paris Siminelakis:
Hashing-Based-Estimators for Kernel Density in High Dimensions. 1032-1043
maintained by 
at 
at 
last updated on 2018-12-14 20:53 CET by the dblp team
data released under the ODC-BY 1.0 license
see also: Terms of Use | Privacy Policy | Imprint