default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID57th FOCS 2016: New Brunswick, New Jersey, USA
- Irit Dinur:
IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, Hyatt Regency, New Brunswick, New Jersey, USA, October 9-11, 2016. IEEE Computer Society 2016, ISBN 978-1-5090-3933-3 - Vipul Goyal, Yuval Ishai, Hemanta K. Maji, Amit Sahai, Alexander A. Sherstov:
Bounded-Communication Leakage Resilience via Parity-Resilient Circuits. 1-10 - Huijia Lin, Vinod Vaikuntanathan:
Indistinguishability Obfuscation from DDH-Like Assumptions on Constant-Degree Graded Encodings. 11-20 - Vipul Goyal, Dakshita Khurana, Amit Sahai:
Breaking the Three Round Barrier for Non-malleable Commitments. 21-30 - Anne Broadbent, Zhengfeng Ji
, Fang Song, John Watrous:
Zero-Knowledge Proof Systems for QMA. 31-40 - Amit Chakrabarti, Sagar Kale:
Strong Fooling Sets for Multi-player Communication with Applications to Deterministic Estimation of Stream Statistics. 41-50 - Djamal Belazzougui, Qin Zhang:
Edit Distance: Sketching, Streaming, and Document Exchange. 51-60 - Kasper Green Larsen, Jelani Nelson, Huy L. Nguyen, Mikkel Thorup:
Heavy Hitters via Cluster-Preserving Clustering. 61-70 - Zohar S. Karnin, Kevin J. Lang, Edo Liberty:
Optimal Quantile Approximation in Streams. 71-78 - Johan Håstad:
An Average-Case Depth Hierarchy Theorem for Higher Depth. 79-88 - 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. 89-98 - Shiteng Chen, Periklis A. Papakonstantinou:
Depth-Reduction for Composites. 99-108 - Ankit Garg, Leonid Gurvits, Rafael Mendes de Oliveira, Avi Wigderson:
A Deterministic Polynomial Time Algorithm for Non-commutative Rational Identity Testing. 109-117 - András Sebö, Anke van Zuylen:
The Salesman's Improved Paths: A 3/2+1/34 Approximation. 118-127 - Michael Elkin, Ofer Neiman:
Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths. 128-137 - Sungjin Im, Shi Li:
Better Unrelated Machine Scheduling for Weighted Completion Time via Random Offsets from Non-uniform Distributions. 138-147 - Yossi Azar, Niv Buchbinder, T.-H. Hubert Chan, Shahar Chen, Ilan Reuven Cohen, Anupam Gupta, Zhiyi Huang, Ning Kang, Viswanath Nagarajan, Joseph Naor, Debmalya Panigrahi:
Online Algorithms for Covering and Packing Problems with Convex Objectives. 148-157 - Eshan Chattopadhyay, Xin Li:
Explicit Non-malleable Extractors, Multi-source Extractors, and Almost Optimal Privacy Amplification Protocols. 158-167 - Xin Li:
Improved Two-Source Extractors, and Affine Extractors for Polylogarithmic Entropy. 168-177 - Gil Cohen, Leonard J. Schulman:
Extractors for Near Logarithmic Min-Entropy. 178-187 - Gil Cohen:
Making the Most of Advice: New Correlation Breakers and Their Applications. 188-196 - Zachary Remscrim:
The Hilbert Function, Algebraic Extractors, and Recursive Fourier Sampling. 197-208 - Shahar Dobzinski:
Computational Efficiency Requires Simple Taxation. 209-218 - Constantinos Daskalakis, Vasilis Syrgkanis:
Learning in Auctions: Regret is Hard, Envy is Easy. 219-228 - Tim Roughgarden, Omri Weinstein:
On the Communication Complexity of Approximate Fixed Points. 229-238 - Yiling Chen, Bo Waggoner:
Informational Substitutes. 239-247 - Alina Ene, Huy L. Nguyen:
Constrained Submodular Maximization: Beyond 1/e. 248-257 - Aviad Rubinstein:
Settling the Complexity of Computing Approximate Two-Player Nash Equilibria. 258-265 - Ran Raz:
Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning. 266-275 - Michael B. Cohen:
Ramanujan Graphs in Polynomial Time. 276-281 - Hamed Hatami, Kaave Hosseini, Shachar Lovett:
Structure of Protocols for XOR Functions. 282-288 - W. T. Gowers, Emanuele Viola:
The Multiparty Communication Complexity of Interleaved Group Products. 289-294 - Susanna F. de Rezende, Jakob Nordström, Marc Vinyals:
How Limited Interaction Hinders Real Communication (and What It Means for Proof and Circuit Complexity). 295-304 - Omri Weinstein, Huacheng Yu:
Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication. 305-314 - 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. 315-324 - Shay Solomon:
Fully Dynamic Maximal Matching in Constant Update Time. 325-334 - Ittai Abraham, David Durfee, Ioannis Koutis, Sebastian Krinninger, Richard Peng:
On Fully Dynamic Graph Sparsifiers. 335-344 - Mathias Bæk Tejs Knudsen:
Linear Hashing Is Awesome. 345-352 - 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. 353-364 - Zachary Friggstad, Mohsen Rezapour, Mohammad R. Salavatipour:
Local Search Yields a PTAS for k-Means in Doubling Metrics. 365-374 - Karl Bringmann, Fabrizio Grandoni, Barna Saha, Virginia Vassilevska Williams:
Truly Sub-cubic Algorithms for Language Edit Distance and RNA-Folding via Fast Bounded-Difference Min-Plus Product. 375-384 - Noam Nisan:
Knuth Prize Lecture: Complexity of Communication in Markets. 385 - Peter Bürgisser, Christian Ikenmeyer, Greta Panova:
No Occurrence Obstructions in Geometric Complexity Theory. 386-395 - Christian Ikenmeyer, Greta Panova:
Rectangular Kronecker Coefficients and Plethysms in Geometric Complexity Theory. 396-405 - Robert Robere, Toniann Pitassi, Benjamin Rossman, Stephen A. Cook:
Exponential Lower Bounds for Monotone Span Programs. 406-415 - Haris Aziz, Simon Mackenzie:
A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents. 416-427 - 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. 428-437 - Tengyu Ma, Jonathan Shi, David Steurer:
Polynomial-Time Tensor Decompositions with Sum-of-Squares. 438-446 - Daniel Dadush, Oded Regev:
Towards Strong Reverse Minkowski-Type Inequalities for Lattices. 447-456 - Arturs Backurs, Piotr Indyk:
Which Regular Expression Patterns Are Hard to Match? 457-466 - Josh Alman, Timothy M. Chan, R. Ryan Williams:
Polynomial Representations of Threshold Functions and Algorithmic Applications. 467-476 - Amir Abboud, Søren Dahlgaard:
Popular Conjectures as a Barrier for Dynamic Planar Graph Algorithms. 477-486 - Ryan M. Rogers, Aaron Roth, Adam D. Smith, Om Thakkar:
Max-Information, Differential Privacy, and Post-selection Hypothesis Testing. 487-494 - Sofya Raskhodnikova, Adam D. Smith:
Lipschitz Extensions for Node-Private Graph Statistics and the Generalized Exponential Mechanism. 495-504 - Yijia Chen, Bingkai Lin:
The Constant Inapproximability of the Parameterized Dominating Set Problem. 505-514 - Fedor V. Fomin, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh:
Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering. 515-524 - Hubie Chen, Matthew Valeriote, Yuichi Yoshida:
Testing Assignments to Constraint Satisfaction Problems. 525-534 - Alexander A. Sherstov:
Compressing Interactive Communication under Product Distributions. 535-544 - Badih Ghazi, Pritish Kamath, Madhu Sudan:
Decidability of Non-interactive Simulation of Joint Distributions. 545-554 - Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha:
Separations in Communication Complexity Using Cheat Sheets and Information Complexity. 555-564 - Mika Göös, Rahul Jain, Thomas Watson:
Extension Complexity of Independent Set Polytopes. 565-572 - Rasmus Kyng, Sushant Sachdeva:
Approximate Gaussian Elimination for Laplacians - Fast, Sparse, and Simple. 573-582 - 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. 583-592 - Aleksander Madry:
Computing Maximum Flow with Augmenting Electrical Flows. 593-602 - Jasper C. H. Lee, Paul Valiant:
Optimizing Star-Convex Functions. 603-614 - Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie:
An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model. 615-624 - Pierre Fraigniaud, Marc Heinrich, Adrian Kosowski:
Local Conflict Coloring. 625-634 - David R. Karger:
A Fast and Simple Unbiased Estimator for Network (Un)reliability. 635-644 - Rafael da Ponte Barbosa, Alina Ene, Huy L. Nguyen, Justin Ward:
A New Framework for Distributed Submodular Maximization. 645-654 - Ilias Diakonikolas, Gautam Kamath, Daniel M. Kane, Jerry Li, Ankur Moitra, Alistair Stewart:
Robust Estimators in High Dimensions without the Computational Intractability. 655-664 - Kevin A. Lai, Anup B. Rao, Santosh S. Vempala:
Agnostic Estimation of Mean and Covariance. 665-674 - Anindya De, Michael E. Saks, Sijian Tang:
Noisy Population Recovery in Polynomial Time. 675-684 - Ilias Diakonikolas, Daniel M. Kane:
A New Approach for Testing Properties of Discrete Distributions. 685-694 - 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. 695-703 - Charilaos Efthymiou, 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. 704-713 - Elizabeth Crosson, Aram W. Harrow:
Simulated Quaotum Annealing Can Be Exponentially Faster Than Classical Simulated Annealing. 714-723 - Allan Sly, Nike Sun, Yumeng Zhang:
The Number of Solutions for Random Regular NAE-SAT. 724-731 - Anand Louis, Santosh S. Vempala:
Accelerated Newton Iteration for Roots of Black Box Polynomials. 732-740 - Xue Chen, Daniel M. Kane, Eric Price, Zhao Song:
Fourier-Sparse Interpolation without a Frequency Gap. 741-750 - Venkatesan Guruswami, David Zuckerman:
Robust Fourier and Polynomial Curve Fitting. 751-759 - Venkata Gandikota, Badih Ghazi, Elena Grigorescu:
NP-Hardness of Reed-Solomon Decoding and the Prouhet-Tarry-Escott Problem. 760-769 - Ofer Grossman, Dana Moshkovitz:
Amplification and Derandomization without Slowdown. 770-779 - Vladimir Kolmogorov:
Commutativity in the Algorithmic Lovász Local Lemma. 780-787 - Nikhil Bansal, Daniel Dadush, Shashwat Garg:
An Algorithm for Komlós Conjecture Matching Banaszczyk's Bound. 788-799 - Jacob Hendricks, Matthew J. Patitz, Trent A. Rogers:
Universal Simulation of Directed Systems in the Abstract Tile Assembly Model Requires Undirectedness. 800-809 - T.-H. Hubert Chan, Shuguang Hu, Shaofeng H.-C. Jiang:
A PTAS for the Steiner Forest Problem in Doubling Metrics. 810-819 - Julia Chuzhoy, Alina Ene:
On Approximating Maximum Independent Set of Rectangles. 820-829
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-12-09 23:25 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
