| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Badih Ghazi, Pritish Kamath, Madhu Sudan 0001 |
Decidability of Non-interactive Simulation of Joint Distributions.  |
FOCS  |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | András Sebö, Anke van Zuylen |
The Salesman's Improved Paths: A 3/2+1/34 Approximation. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Aleksander Madry |
Computing Maximum Flow with Augmenting Electrical Flows. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Sungjin Im, Shi Li 0001 |
Better Unrelated Machine Scheduling for Weighted Completion Time via Random Offsets from Non-uniform Distributions. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Rafael da Ponte Barbosa, Alina Ene, Huy L. Nguyen, Justin Ward |
A New Framework for Distributed Submodular Maximization. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain 0001, Robin Kothari, Troy Lee, Miklos Santha |
Separations in Communication Complexity Using Cheat Sheets and Information Complexity. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Zachary Remscrim |
The Hilbert Function, Algebraic Extractors, and Recursive Fourier Sampling. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael B. Cohen, Jonathan A. Kelner, John Peebles, Richard Peng, Aaron Sidford, Adrian Vladu |
Faster Algorithms for Computing the Stationary Distribution, Simulating Random Walks, and More. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Charilaos Efthymiou 0001, Thomas P. Hayes, Daniel Stefankovic, Eric Vigoda, Yitong Yin |
Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Gil Cohen |
Making the Most of Advice: New Correlation Breakers and Their Applications. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Christian Ikenmeyer, Greta Panova |
Rectangular Kronecker Coefficients and Plethysms in Geometric Complexity Theory. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Ittai Abraham, David Durfee, Ioannis Koutis, Sebastian Krinninger, Richard Peng |
On Fully Dynamic Graph Sparsifiers. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Rasmus Kyng, Sushant Sachdeva |
Approximate Gaussian Elimination for Laplacians - Fast, Sparse, and Simple. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Magnus Gausdal Find, Alexander Golovnev, Edward A. Hirsch, Alexander S. Kulikov |
A Better-Than-3n Lower Bound for the Circuit Complexity of an Explicit Function. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Shahar Dobzinski |
Computational Efficiency Requires Simple Taxation. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Vincent Cohen-Addad, Philip N. Klein, Claire Mathieu |
Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Djamal Belazzougui, Qin Zhang 0001 |
Edit Distance: Sketching, Streaming, and Document Exchange. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Nikhil Bansal 0001, Daniel Dadush, Shashwat Garg |
An Algorithm for Komlós Conjecture Matching Banaszczyk's Bound. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Karl Bringmann, Fabrizio Grandoni 0001, Barna Saha, Virginia Vassilevska Williams |
Truly Sub-cubic Algorithms for Language Edit Distance and RNA-Folding via Fast Bounded-Difference Min-Plus Product. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano, Jakub Lacki, Nikos Parotsidis |
Decremental Single-Source Reachability and Strongly Connected Components in Õ(m√n) Total Update Time. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | David R. Karger |
A Fast and Simple Unbiased Estimator for Network (Un)reliability. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Shay Solomon |
Fully Dynamic Maximal Matching in Constant Update Time. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Vipul Goyal, Yuval Ishai, Hemanta K. Maji, Amit Sahai, Alexander A. Sherstov |
Bounded-Communication Leakage Resilience via Parity-Resilient Circuits. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Ankit Garg, Leonid Gurvits, Rafael Mendes de Oliveira, Avi Wigderson |
A Deterministic Polynomial Time Algorithm for Non-commutative Rational Identity Testing. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Ran Raz |
Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Arturs Backurs, Piotr Indyk |
Which Regular Expression Patterns Are Hard to Match? |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | T.-H. Hubert Chan, Shuguang Hu, Shaofeng H.-C. Jiang |
A PTAS for the Steiner Forest Problem in Doubling Metrics. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Anand Louis, Santosh S. Vempala |
Accelerated Newton Iteration for Roots of Black Box Polynomials. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Vipul Goyal, Dakshita Khurana, Amit Sahai |
Breaking the Three Round Barrier for Non-malleable Commitments. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Yiling Chen 0001, Bo Waggoner |
Informational Substitutes. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Fedor V. Fomin, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh 0001 |
Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Pierre Fraigniaud, Marc Heinrich, Adrian Kosowski |
Local Conflict Coloring. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Daniel Dadush, Oded Regev 0001 |
Towards Strong Reverse Minkowski-Type Inequalities for Lattices. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Amir Abboud, Søren Dahlgaard |
Popular Conjectures as a Barrier for Dynamic Planar Graph Algorithms. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | W. T. Gowers 0001, Emanuele Viola |
The Multiparty Communication Complexity of Interleaved Group Products. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Xue Chen 0001, Daniel M. Kane, Eric Price 0001, Zhao Song 0002 |
Fourier-Sparse Interpolation without a Frequency Gap. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Tim Roughgarden, Omri Weinstein |
On the Communication Complexity of Approximate Fixed Points. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Sofya Raskhodnikova, Adam D. Smith |
Lipschitz Extensions for Node-Private Graph Statistics and the Generalized Exponential Mechanism. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Kasper Green Larsen, Jelani Nelson, Huy L. Nguyen, Mikkel Thorup |
Heavy Hitters via Cluster-Preserving Clustering. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Shiteng Chen, Periklis A. Papakonstantinou |
Depth-Reduction for Composites. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Yijia Chen, Bingkai Lin |
The Constant Inapproximability of the Parameterized Dominating Set Problem. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Boaz Barak, Samuel B. Hopkins, Jonathan A. Kelner, Pravesh Kothari, Ankur Moitra, Aaron Potechin |
A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Alina Ene, Huy L. Nguyen |
Constrained Submodular Maximization: Beyond 1/e. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Eshan Chattopadhyay, Xin Li 0006 |
Explicit Non-malleable Extractors, Multi-source Extractors, and Almost Optimal Privacy Amplification Protocols. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Jacob Hendricks, Matthew J. Patitz, Trent A. Rogers |
Universal Simulation of Directed Systems in the Abstract Tile Assembly Model Requires Undirectedness. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Noam Nisan |
Knuth Prize Lecture: Complexity of Communication in Markets. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Jasper C. H. Lee, Paul Valiant |
Optimizing Star-Convex Functions. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Kevin A. Lai, Anup B. Rao, Santosh S. Vempala |
Agnostic Estimation of Mean and Covariance. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Amit Chakrabarti, Sagar Kale |
Strong Fooling Sets for Multi-player Communication with Applications to Deterministic Estimation of Stream Statistics. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Xin Li 0006 |
Improved Two-Source Extractors, and Affine Extractors for Polylogarithmic Entropy. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Susanna F. de Rezende, Jakob Nordström, Marc Vinyals |
How Limited Interaction Hinders Real Communication (and What It Means for Proof and Circuit Complexity). |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Anindya De, Michael E. Saks, Sijian Tang |
Noisy Population Recovery in Polynomial Time. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Zachary Friggstad, Mohsen Rezapour, Mohammad R. Salavatipour |
Local Search Yields a PTAS for k-Means in Doubling Metrics. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Tengyu Ma 0001, Jonathan Shi, David Steurer |
Polynomial-Time Tensor Decompositions with Sum-of-Squares. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Constantinos Daskalakis, Vasilis Syrgkanis |
Learning in Auctions: Regret is Hard, Envy is Easy. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael Elkin, Ofer Neiman |
Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Ilias Diakonikolas, Daniel M. Kane |
A New Approach for Testing Properties of Discrete Distributions. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Irit Dinur (eds.) |
IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA |
FOCS |
2016 |
DBLP BibTeX RDF |
|
| 1 | Peter Bürgisser, Christian Ikenmeyer, Greta Panova |
No Occurrence Obstructions in Geometric Complexity Theory. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Josh Alman, Timothy M. Chan, R. Ryan Williams |
Polynomial Representations of Threshold Functions and Algorithmic Applications. |
FOCS |
2016 |
DBLP DOI BibTeX RDF |
|
| 1 | Mika Göös, Toniann Pitassi, Thomas Watson 0001 |
Deterministic Communication vs. Partition Number. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Jakub Gajarský, Petr Hlinený, Daniel Lokshtanov, Jan Obdrzálek, Sebastian Ordyniak, M. S. Ramanujan 0001, Saket Saurabh 0001 |
FO Model Checking on Posets of Bounded Width. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael A. Forbes 0001 |
Deterministic Divisibility Testing via Shifted Partial Derivatives. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Nir Bitansky, Vinod Vaikuntanathan |
Indistinguishability Obfuscation from Functional Encryption. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Vladimir Kolmogorov, Andrei A. Krokhin, Michal Rolínek |
The Complexity of General-Valued CSPs. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Sungjin Im, Janardhan Kulkarni, Kamesh Munagala |
Competitive Flow Time Algorithms for Polyhedral Scheduling. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Dominic W. Berry, Andrew M. Childs, Robin Kothari |
Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Timothy M. Chan, Yakov Nekrich |
Towards an Optimal Method for Dynamic Planar Point Location. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Nir Bitansky, Omer Paneth, Alon Rosen |
On the Cryptographic Hardness of Finding a Nash Equilibrium. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Pu Gao, Nicholas C. Wormald |
Uniform Generation of Random Regular Graphs. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Gilad Asharov, Gil Segev 0001 |
Limits on the Power of Indistinguishability Obfuscation and Functional Encryption. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Adam W. Marcus, Daniel A. Spielman, Nikhil Srivastava |
Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Micha Sharir, Noam Solomon |
Incidences between Points and Lines in R^4. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Eva Rotenberg, Mikkel Thorup |
Hashing for Statistics over K-Partitions. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Moran Feldman, Rico Zenklusen |
The Submodular Secretary Problem Goes Linear. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams |
If the Current Clique Algorithms are Optimal, So is Valiant's Parser. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Saeed Alaei, Jason D. Hartline, Rad Niazadeh, Emmanouil Pountourakis, Yang Yuan |
Optimal Auctions vs. Anonymous Pricing. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Shay Moran, Amir Shpilka, Avi Wigderson, Amir Yehudayoff |
Compressing and Teaching for Low VC-Dimension. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Nicholas J. A. Harvey, Jan Vondrák |
An Algorithmic Proof of the Lovasz Local Lemma via Resampling Oracles. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Cynthia Dwork, Adam D. Smith, Thomas Steinke 0002, Jonathan R. Ullman, Salil P. Vadhan |
Robust Traceability from Trace Amounts. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Talya Eden, Amit Levi, Dana Ron, C. Seshadhri 0001 |
Approximately Counting Triangles in Sublinear Time. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Nima Anari, Shayan Oveis Gharan |
Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric TSP. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Charles Bordenave, Marc Lelarge, Laurent Massoulié |
Non-backtracking Spectrum of Random Graphs: Community Detection and Non-regular Ramanujan Graphs. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Alina Ene, Deeparnab Chakrabarty, Ravishankar Krishnaswamy, Debmalya Panigrahi |
Online Buy-at-Bulk Network Design. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan |
An Average-Case Depth Hierarchy Theorem for Boolean Circuits. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Parikshit Gopalan, Daniel M. Kane, Raghu Meka |
Pseudorandomness via the Discrete Fourier Transform. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Jin-Yi Cai, Zhiguo Fu, Heng Guo 0001, Tyson Williams |
A Holant Dichotomy: Is the FKT Algorithm Universal? |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Lee-Ad Gottlieb |
A Light Metric Spanner. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Josh Alman, Ryan Williams 0001 |
Probabilistic Polynomials and Hamming Nearest Neighbors. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Sarah R. Allen, Ryan O'Donnell, David Witmer |
How to Refute a Random CSP. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Raphaël Clifford, Allan Grønlund, Kasper Green Larsen |
New Unconditional Hardness Results for Dynamic and Online Problems. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Leonard J. Schulman, Alistair Sinclair, Piyush Srivastava 0001 |
Symbolic Integration and the Complexity of Computing Averages. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Karl Bringmann, Marvin Künnemann |
Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Mikkel Thorup |
Sample (x) = (a*x<=t) is a Distinguisher with Probability 1/8. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Amir Nayyeri, Benjamin Raichel |
Reality Distortion: Exact and Approximate Algorithms for Embedding into the Line. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Ruoyu Sun 0001, Zhi-Quan Luo |
Guaranteed Matrix Completion via Nonconvex Factorization. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Jacob Holm, Eva Rotenberg, Mikkel Thorup |
Planar Reachability in Linear Space and Constant Time. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Vitaly Feldman, Jan Vondrák |
Tight Bounds on Low-Degree Spectral Concentration of Submodular and XOS Functions. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Divesh Aggarwal, Daniel Dadush, Noah Stephens-Davidowitz |
Solving the Closest Vector Problem in 2^n Time - The Discrete Gaussian Strikes Again! |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
| 1 | Benjamin Rossman |
The Average Sensitivity of Bounded-Depth Formulas. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")
data released under the ODC-BY 1.0 license