IEEE Foundations of Computer Science, FOCS 2017


The information below was collected semi-automatically. The authors have not yet been given the opportunity to verify the data.
[?] We ask all authors to verify the information we have about their papers, in particular the location of any supporting artifacts. We send out emails to authors asking them to update or verify this information incrementally, one conference at a time. For conferences where these emails have yet to be sent out we present the information in gray text.
Title/Authors Title Research Artifacts
[?] A research artifact is any by-product of a research project that is not directly included in the published research paper. In Computer Science research this is often source code and data sets, but it could also be media, documentation, inputs to proof assistants, shell-scripts to run experiments, etc.
Details

Removing Depth-Order Cycles among Triangles: An Efficient Algorithm Generating Triangular Fragments

Mark de Berg

Removing Depth-Order Cycles among Triangles: An Efficient Algorithm Generating Triangular Fragments

Details
Discussion Comments: 0
Verification: Author has not verified information

How to Achieve Non-Malleability in One or Two Rounds

Dakshita Khurana, Amit Sahai

How to Achieve Non-Malleability in One or Two Rounds

Details
Discussion Comments: 0
Verification: Authors have not verified information

Two-Round and Non-Interactive Concurrent Non-Malleable Commitments from Time-Lock Puzzles

Huijia Lin, Rafael Pass, Pratik Soni

Two-Round and Non-Interactive Concurrent Non-Malleable Commitments from Time-Lock Puzzles

Details
Discussion Comments: 0
Verification: Authors have not verified information

Tight Lower Bounds for Differentially Private Selection

Thomas Steinke, Jonathan Ullman

Tight Lower Bounds for Differentially Private Selection

Details
Discussion Comments: 0
Verification: Authors have not verified information

Random Formulas, Monotone Circuits, and Interpolation

Pavel Hrubes, Pavel Pudlák

Random Formulas, Monotone Circuits, and Interpolation

Details
Discussion Comments: 0
Verification: Authors have not verified information

Eldan's Stochastic Localization and the KLS Hyperplane Conjecture: An Improved Lower Bound for Expansion

Yin Tat Lee, Santosh Srinivas Vempala

Eldan's Stochastic Localization and the KLS Hyperplane Conjecture: An Improved Lower Bound for Expansion

Details
Discussion Comments: 0
Verification: Authors have not verified information

Hashing-Based-Estimators for Kernel Density in High Dimensions

Moses Charikar, Paris Siminelakis

Hashing-Based-Estimators for Kernel Density in High Dimensions

Details
Discussion Comments: 0
Verification: Authors have not verified information

Sample Efficient Estimation and Recovery in Sparse FFT via Isolation on Average

Michael Kapralov

Sample Efficient Estimation and Recovery in Sparse FFT via Isolation on Average

Details
Discussion Comments: 0
Verification: Author has not verified information

Weighted k-Server Bounds via Combinatorial Dichotomies

Nikhil Bansal, Marek Eliás, Grigorios Koumoutsos

Weighted k-Server Bounds via Combinatorial Dichotomies

Details
Discussion Comments: 0
Verification: Authors have not verified information

Matrix Scaling and Balancing via Box Constrained Newton's Method and Interior Point Methods

Michael B. Cohen, Aleksander Madry, Dimitris Tsipras, Adrian Vladu

Matrix Scaling and Balancing via Box Constrained Newton's Method and Interior Point Methods

Details
Discussion Comments: 0
Verification: Authors have not verified information

Lockable Obfuscation

Rishab Goyal, Venkata Koppula, Brent Waters

Lockable Obfuscation

Details
Discussion Comments: 0
Verification: Authors have not verified information

On Small-Depth Frege Proofs for Tseitin for Grids

Johan Håstad

On Small-Depth Frege Proofs for Tseitin for Grids

Details
Discussion Comments: 0
Verification: Author has not verified information

Optimal Lower Bounds for Universal Relation, and for Samplers and Finding Duplicates in Streams

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

Details
Discussion Comments: 0
Verification: Authors have not verified information

On the Power of Statistical Zero Knowledge

Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, Prashant Nalini Vasudevan

On the Power of Statistical Zero Knowledge

Details
Discussion Comments: 0
Verification: Authors have not verified information

A Time Hierarchy Theorem for the LOCAL Model

Yi-Jun Chang, Seth Pettie

A Time Hierarchy Theorem for the LOCAL Model

Details
Discussion Comments: 0
Verification: Authors have not verified information

Fast & Space-Efficient Approximations of Language Edit Distance and RNA Folding: An Amnesic Dynamic Programming Approach

Barna Saha

Fast & Space-Efficient Approximations of Language Edit Distance and RNA Folding: An Amnesic Dynamic Programming Approach

Details
Discussion Comments: 0
Verification: Author has not verified information

Robust Polynomial Regression up to the Information Theoretic Limit

Daniel Kane, Sushrut Karmalkar, Eric Price

Robust Polynomial Regression up to the Information Theoretic Limit

Details
Discussion Comments: 0
Verification: Authors have not verified information

Fast Similarity Sketching

Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Mikkel Thorup

Fast Similarity Sketching

Details
Discussion Comments: 0
Verification: Authors have not verified information

Oracle-Efficient Online Learning and Auction Design

Miroslav Dudík, Nika Haghtalab, Haipeng Luo, Robert E. Schapire, Vasilis Syrgkanis, Jennifer Wortman Vaughan

Oracle-Efficient Online Learning and Auction Design

Details
Discussion Comments: 0
Verification: Authors have not verified information

Active Classification with Comparison Queries

Daniel M. Kane, Shachar Lovett, Shay Moran, Jiapeng Zhang

Active Classification with Comparison Queries

Details
Discussion Comments: 0
Verification: Authors have not verified information

Determinant-Preserving Sparsification of SDDM Matrices with Applications to Counting and Sampling Spanning Trees

David Durfee, John Peebles, Richard Peng, Anup B. Rao

Determinant-Preserving Sparsification of SDDM Matrices with Applications to Counting and Sampling Spanning Trees

Details
Discussion Comments: 0
Verification: Authors have not verified information

Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms

Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, Justin Ward

Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms

Details
Discussion Comments: 0
Verification: Authors have not verified information

The Power of Sum-of-Squares for Detecting Hidden Structures

Samuel B. Hopkins, Pravesh K. Kothari, Aaron Potechin, Prasad Raghavendra, Tselil Schramm, David Steurer

The Power of Sum-of-Squares for Detecting Hidden Structures

Details
Discussion Comments: 0
Verification: Authors have not verified information

Variable-Version Lovász Local Lemma: Beyond Shearer's Bound

Kun He, Liang Li, Xingwu Liu, Yuyi Wang, Mingji Xia

Variable-Version Lovász Local Lemma: Beyond Shearer's Bound

Details
Discussion Comments: 0
Verification: Authors have not verified information

First Efficient Convergence for Streaming k-PCA: A Global, Gap-Free, and Near-Optimal Rate

Zeyuan Allen-Zhu, Yuanzhi Li

First Efficient Convergence for Streaming k-PCA: A Global, Gap-Free, and Near-Optimal Rate

Details
Discussion Comments: 0
Verification: Authors have not verified information

A Dichotomy Theorem for Nonuniform CSPs

Andrei A. Bulatov

A Dichotomy Theorem for Nonuniform CSPs

Details
Discussion Comments: 0
Verification: Author has not verified information

On Preparing Ground States of Gapped Hamiltonians: An Efficient Quantum Lovász Local Lemma

András Pal Gilyén, Or Sattath

On Preparing Ground States of Gapped Hamiltonians: An Efficient Quantum Lovász Local Lemma

Details
Discussion Comments: 0
Verification: Authors have not verified information

Optimal Repair of Reed-Solomon Codes: Achieving the Cut-Set Bound

Itzhak Tamo, Min Ye, Alexander Barg

Optimal Repair of Reed-Solomon Codes: Achieving the Cut-Set Bound

Details
Discussion Comments: 0
Verification: Authors have not verified information

Much Faster Algorithms for Matrix Scaling

Zeyuan Allen-Zhu, Yuanzhi Li, Rafael Mendes de Oliveira, Avi Wigderson

Much Faster Algorithms for Matrix Scaling

Details
Discussion Comments: 0
Verification: Authors have not verified information

Distributed PCP Theorems for Hardness of Approximation in P

Amir Abboud, Aviad Rubinstein, R. Ryan Williams

Distributed PCP Theorems for Hardness of Approximation in P

Details
Discussion Comments: 0
Verification: Authors have not verified information

Quantum SDP-Solvers: Better Upper and Lower Bounds

Joran van Apeldoorn, András Gilyén, Sander Gribling, Ronald de Wolf

Quantum SDP-Solvers: Better Upper and Lower Bounds

Details
Discussion Comments: 0
Verification: Authors have not verified information

Learning Graphical Models Using Multiplicative Weights

Adam R. Klivans, Raghu Meka

Learning Graphical Models Using Multiplicative Weights

Details
Discussion Comments: 0
Verification: Authors have not verified information

A Dichotomy for Regular Expression Membership Testing

Karl Bringmann, Allan Grønlund, Kasper Green Larsen

A Dichotomy for Regular Expression Membership Testing

Details
Discussion Comments: 0
Verification: Authors have not verified information

An Input Sensitive Online Algorithm for the Metric Bipartite Matching Problem

Krati Nayyar, Sharath Raghvendra

An Input Sensitive Online Algorithm for the Metric Bipartite Matching Problem

Details
Discussion Comments: 0
Verification: Authors have not verified information

Capacity of Neural Networks for Lifelong Learning of Composable Tasks

Leslie G. Valiant

Capacity of Neural Networks for Lifelong Learning of Composable Tasks

Details
Discussion Comments: 0
Verification: Author has not verified information

On Learning Mixtures of Well-Separated Gaussians

Oded Regev, Aravindan Vijayaraghavan

On Learning Mixtures of Well-Separated Gaussians

Details
Discussion Comments: 0
Verification: Authors have not verified information

Exponentially-Hard Gap-CSP and Local PRG via Local Hardcore Functions

Benny Applebaum

Exponentially-Hard Gap-CSP and Local PRG via Local Hardcore Functions

Details
Discussion Comments: 0
Verification: Author has not verified information

Linear Algebraic Analogues of the Graph Isomorphism Problem and the Erdős-Rényi Model

Yinan Li, Youming Qiao

Linear Algebraic Analogues of the Graph Isomorphism Problem and the Erdős-Rényi Model

Details
Discussion Comments: 0
Verification: Authors have not verified information

Approximating the Held-Karp Bound for Metric TSP in Nearly-Linear Time

Chandra Chekuri, Kent Quanrud

Approximating the Held-Karp Bound for Metric TSP in Nearly-Linear Time

Details
Discussion Comments: 0
Verification: Authors have not verified information

The Independence Number of the Birkhoff Polytope Graph, and Applications to Maximally Recoverable Codes

Daniel Kane, Shachar Lovett, Sankeerth Rao

The Independence Number of the Birkhoff Polytope Graph, and Applications to Maximally Recoverable Codes

Details
Discussion Comments: 0
Verification: Authors have not verified information

Optimality of the Johnson-Lindenstrauss Lemma

Kasper Green Larsen, Jelani Nelson

Optimality of the Johnson-Lindenstrauss Lemma

Details
Discussion Comments: 0
Verification: Authors have not verified information

Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations

Shi Li

Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations

Details
Discussion Comments: 0
Verification: Author has not verified information

A Characterization of Testable Hypergraph Properties

Felix Joos, Jaehoon Kim, Daniela Kühn, Deryk Osthus

A Characterization of Testable Hypergraph Properties

Details
Discussion Comments: 0
Verification: Authors have not verified information

Optimal Interactive Coding for Insertions, Deletions, and Substitutions

Alexander A. Sherstov, Pei Wu

Optimal Interactive Coding for Insertions, Deletions, and Substitutions

Details
Discussion Comments: 0
Verification: Authors have not verified information

Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices

Cameron Musco, David P. Woodruff

Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices

Details
Discussion Comments: 0
Verification: Authors have not verified information

Boolean Unateness Testing with Õ(n3/4) Adaptive Queries

Xi Chen, Erik Waingarten, Jinyu Xie

Boolean Unateness Testing with Õ(n3/4) Adaptive Queries

Details
Discussion Comments: 0
Verification: Authors have not verified information

Local List Recovery of High-Rate Tensor Codes & Applications

Brett Hemenway, Noga Ron-Zewi, Mary Wootters

Local List Recovery of High-Rate Tensor Codes & Applications

Details
Discussion Comments: 0
Verification: Authors have not verified information

Optimal Las Vegas Locality Sensitive Data Structures

Thomas Dybdahl Ahle

Optimal Las Vegas Locality Sensitive Data Structures

Details
Discussion Comments: 0
Verification: Author has not verified information

Local Hamiltonians Whose Ground States Are Hard to Approximate

Lior Eldar, Aram Wettroth Harrow

Local Hamiltonians Whose Ground States Are Hard to Approximate

Details
Discussion Comments: 0
Verification: Authors have not verified information

Dynamic Minimum Spanning Forest with Subpolynomial Worst-Case Update Time

Danupon Nanongkai, Thatchaphol Saranurak, Christian Wulff-Nilsen

Dynamic Minimum Spanning Forest with Subpolynomial Worst-Case Update Time

Details
Discussion Comments: 0
Verification: Authors have not verified information

A Time-Space Lower Bound for a Large Class of Learning Problems

Ran Raz

A Time-Space Lower Bound for a Large Class of Learning Problems

Details
Discussion Comments: 0
Verification: Author has not verified information

Short Presburger Arithmetic Is Hard

Danny Nguyen, Igor Pak

Short Presburger Arithmetic Is Hard

Details
Discussion Comments: 0
Verification: Authors have not verified information

Approximating Geometric Knapsack via L-Packings

Waldo Gálvez, Fabrizio Grandoni, Sandy Heydrich, Salvatore Ingala, Arindam Khan, Andreas Wiese

Approximating Geometric Knapsack via L-Packings

Details
Discussion Comments: 0
Verification: Authors have not verified information

Minor-Free Graphs Have Light Spanners

Glencora Borradaile, Hung Le, Christian Wulff-Nilsen

Minor-Free Graphs Have Light Spanners

Details
Discussion Comments: 0
Verification: Authors have not verified information

Quantum Speed-Ups for Solving Semidefinite Programs

Fernando G. S. L. Brandão, Krysta M. Svore

Quantum Speed-Ups for Solving Semidefinite Programs

Details
Discussion Comments: 0
Verification: Authors have not verified information

Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-and-Solve

Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann

Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-and-Solve

Details
Discussion Comments: 0
Verification: Authors have not verified information

On the Quantitative Hardness of CVP

Huck Bennett, Alexander Golovnev, Noah Stephens-Davidowitz

On the Quantitative Hardness of CVP

Details
Discussion Comments: 0
Verification: Authors have not verified information

Query-to-Communication Lifting for BPP

Mika Göös, Toniann Pitassi, Thomas Watson

Query-to-Communication Lifting for BPP

Details
Discussion Comments: 0
Verification: Authors have not verified information

Polylogarithmic Approximation for Minimum Planarization (Almost)

Ken-ichi Kawarabayashi, Anastasios Sidiropoulos

Polylogarithmic Approximation for Minimum Planarization (Almost)

Details
Discussion Comments: 0
Verification: Authors have not verified information

Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Non-Stochastic Inputs

Paul Duetting, Michal Feldman, Thomas Kesselheim, Brendan Lucier

Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Non-Stochastic Inputs

Details
Discussion Comments: 0
Verification: Authors have not verified information

Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures

Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart

Statistical Query Lower Bounds for Robust Estimation of High-Dimensional Gaussians and Gaussian Mixtures

Details
Discussion Comments: 0
Verification: Authors have not verified information

Deterministic Distributed Edge-Coloring via Hypergraph Maximal Matching

Manuela Fischer, Mohsen Ghaffari, Fabian Kuhn

Deterministic Distributed Edge-Coloring via Hypergraph Maximal Matching

Details
Discussion Comments: 0
Verification: Authors have not verified information

Optimal Compression of Approximate Inner Products and Dimension Reduction

Noga Alon, Bo'az Klartag

Optimal Compression of Approximate Inner Products and Dimension Reduction

Details
Discussion Comments: 0
Verification: Authors have not verified information

Learning Multi-Item Auctions with (or without) Samples

Yang Cai, Constantinos Daskalakis

Learning Multi-Item Auctions with (or without) Samples

Details
Discussion Comments: 0
Verification: Authors have not verified information

Obfuscating Compute-and-Compare Programs under LWE

Daniel Wichs, Giorgos Zirdelis

Obfuscating Compute-and-Compare Programs under LWE

Details
Discussion Comments: 0
Verification: Authors have not verified information

Faster (and Still Pretty Simple) Unbiased Estimators for Network (Un)reliability

David R. Karger

Faster (and Still Pretty Simple) Unbiased Estimators for Network (Un)reliability

Details
Discussion Comments: 0
Verification: Author has not verified information

From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More

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

Details
Discussion Comments: 0
Verification: Authors have not verified information

High Dimensional Expanders Imply Agreement Expanders

Irit Dinur, Tali Kaufman

High Dimensional Expanders Imply Agreement Expanders

Details
Discussion Comments: 0
Verification: Authors have not verified information

Distributed Exact Weighted All-Pairs Shortest Paths in Õ(n5/4) Rounds

Chien-Chung Huang, Danupon Nanongkai, Thatchaphol Saranurak

Distributed Exact Weighted All-Pairs Shortest Paths in Õ(n5/4) Rounds

Details
Discussion Comments: 0
Verification: Authors have not verified information

A Nearly Optimal Lower Bound on the Approximate Degree of AC0

Mark Bun, Justin Thaler

A Nearly Optimal Lower Bound on the Approximate Degree of AC0

Details
Discussion Comments: 0
Verification: Authors have not verified information

Subdeterminant Maximization via Nonconvex Relaxations and Anti-Concentration

Javad B. Ebrahimi, Damian Straszak, Nisheeth K. Vishnoi

Subdeterminant Maximization via Nonconvex Relaxations and Anti-Concentration

Details
Discussion Comments: 0
Verification: Authors have not verified information

Deterministic Search for CNF Satisfying Assignments in Almost Polynomial Time

Rocco A. Servedio, Li-Yang Tan

Deterministic Search for CNF Satisfying Assignments in Almost Polynomial Time

Details
Discussion Comments: 0
Verification: Authors have not verified information

Fast and Compact Exact Distance Oracle for Planar Graphs

Vincent Cohen-Addad, Søren Dahlgaard, Christian Wulff-Nilsen

Fast and Compact Exact Distance Oracle for Planar Graphs

Details
Discussion Comments: 0
Verification: Authors have not verified information

The Ising Partition Function: Zeros and Deterministic Approximation

Jingcheng Liu, Alistair Sinclair, Piyush Srivastava

The Ising Partition Function: Zeros and Deterministic Approximation

Details
Discussion Comments: 0
Verification: Authors have not verified information

Efficient Bayesian Estimation from Few Samples: Community Detection and Related Problems

Samuel B. Hopkins, David Steurer

Efficient Bayesian Estimation from Few Samples: Community Detection and Related Problems

Details
Discussion Comments: 0
Verification: Authors have not verified information

Fooling Intersections of Low-Weight Halfspaces

Rocco A. Servedio, Li-Yang Tan

Fooling Intersections of Low-Weight Halfspaces

Details
Discussion Comments: 0
Verification: Authors have not verified information

Weak Decoupling, Polynomial Folds and Approximate Optimization over the Sphere

Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani

Weak Decoupling, Polynomial Folds and Approximate Optimization over the Sphere

Details
Discussion Comments: 0
Verification: Authors have not verified information

Hardness Results for Structured Linear Systems

Rasmus Kyng, Peng Zhang

Hardness Results for Structured Linear Systems

Details
Discussion Comments: 0
Verification: Authors have not verified information

White-Box vs. Black-Box Complexity of Search Problems: Ramsey and Graph Property Testing

Ilan Komargodski, Moni Naor, Eylon Yogev

White-Box vs. Black-Box Complexity of Search Problems: Ramsey and Graph Property Testing

Details
Discussion Comments: 0
Verification: Authors have not verified information

On the Local Structure of Stable Clustering Instances

Vincent Cohen-Addad, Chris Schwiegelshohn

On the Local Structure of Stable Clustering Instances

Details
Discussion Comments: 0
Verification: Authors have not verified information

Random Θ(log n)-CNFs Are Hard for Cutting Planes

Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere

Random Θ(log n)-CNFs Are Hard for Cutting Planes

Details
Discussion Comments: 0
Verification: Authors have not verified information

Generalized Uniformity Testing

Tugkan Batu, Clément L. Canonne

Generalized Uniformity Testing

Details
Discussion Comments: 0
Verification: Authors have not verified information

Derandomization Beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space

Jack Murtagh, Omer Reingold, Aaron Sidford, Salil P. Vadhan

Derandomization Beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space

Details
Discussion Comments: 0
Verification: Authors have not verified information

The Matching Problem in General Graphs Is in Quasi-NC

Ola Svensson, Jakub Tarnawski

The Matching Problem in General Graphs Is in Quasi-NC

Details
Discussion Comments: 0
Verification: Authors have not verified information

Garbled Protocols and Two-Round MPC from Bilinear Maps

Sanjam Garg, Akshayaram Srinivasan

Garbled Protocols and Two-Round MPC from Bilinear Maps

Details
Discussion Comments: 0
Verification: Authors have not verified information

A Rounds vs. Communication Tradeoff for Multi-Party Set Disjointness

Mark Braverman, Rotem Oshman

A Rounds vs. Communication Tradeoff for Multi-Party Set Disjointness

Details
Discussion Comments: 0
Verification: Authors have not verified information

A Proof of CSP Dichotomy Conjecture

Dmitriy Zhuk

A Proof of CSP Dichotomy Conjecture

Details
Discussion Comments: 0
Verification: Author has not verified information

Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices

Nima Anari, Leonid Gurvits, Shayan Oveis Gharan, Amin Saberi

Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices

Details
Discussion Comments: 0
Verification: Authors have not verified information

Testing Hereditary Properties of Ordered Graphs and Matrices

Noga Alon, Omri Ben-Eliezer, Eldar Fischer

Testing Hereditary Properties of Ordered Graphs and Matrices

Details
Discussion Comments: 0
Verification: Authors have not verified information

Average-Case Reconstruction for the Deletion Channel: Subpolynomially Many Traces Suffice

Yuval Peres, Alex Zhai

Average-Case Reconstruction for the Deletion Channel: Subpolynomially Many Traces Suffice

Details
Discussion Comments: 0
Verification: Authors have not verified information