default search action
54th FOCS 2013: Berkeley, CA, USA
- 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA. IEEE Computer Society 2013, ISBN 978-0-7695-5135-7
- Noa Avigdor-Elgrabli, Yuval Rabani
:
An optimal randomized online algorithm for reordering buffer management. 1-10 - Ashish Chiplunkar, Sundar Vishwanathan:
On Randomized Memoryless Algorithms for the Weighted K-Server Problem. 11-19 - Thomas Rothvoß:
Approximating Bin Packing within O(log OPT * Log Log OPT) Bins. 20-29 - Joseph Cheriyan, László A. Végh
Approximating Minimum-Cost k-Node Connected Subgraphs via Independence-Free Graphs. 30-39 - Sanjam Garg
Candidate Indistinguishability Obfuscation and Functional Encryption for all Circuits. 40-49 - Kai-Min Chung
Constant-Round Concurrent Zero Knowledge from P-Certificates. 50-59 - Kai-Min Chung
Simultaneous Resettability from One-Way Functions. 60-69 - Ran Canetti, Huijia Lin, Rafael Pass
From Unprovability to Environmentally Friendly Protocols. 70-79 - Rasmus Pagh, Gil Segev, Udi Wieder:
How to Approximate a Set without Knowing Its Size in Advance. 80-89 - Mikkel Thorup
Simple Tabulation, Fast Expanders, Double Tabulation, and High Independence. 90-99 - Xin Li:
Extractors for a Constant Number of Independent Sources with Polylogarithmic Min-Entropy. 100-109 - Ankur Moitra, Michael E. Saks:
A Polynomial Time Algorithm for Lossy Population Recovery. 110-116 - Jelani Nelson, Huy L. Nguyen:
OSNAP: Faster Numerical Linear Algebra Algorithms via Sparser Subspace Embeddings. 117-126 - Mu Li, Gary L. Miller, Richard Peng:
Iterative Row Sampling. 127-136 - Harold N. Gabow, Piotr Sankowski:
Algebraic Algorithms for B-Matching, Shortest Undirected Paths, and F-Factors. 137-146 - Yin Tat Lee, Aaron Sidford:
Efficient Accelerated Coordinate Descent Methods and Faster Algorithms for Solving Linear Systems. 147-156 - László Babai
Faster Canonical Forms for Strongly Regular Graphs. 157-166 - Chandra Chekuri, Anastasios Sidiropoulos:
Approximation Algorithms for Euler Genus and Related Problems. 167-176 - Anastasios Sidiropoulos:
Non-positive Curvature and the Planar Embedding Conjecture. 177-186 - Ken-ichi Kawarabayashi, Yusuke Kobayashi:
All-or-Nothing Multicommodity Flow Problem with Bounded Fractionality in Planar Graphs. 187-196 - Marek Cygan
The Planar Directed K-Vertex-Disjoint Paths Problem Is Fixed-Parameter Tractable. 197-206 - Ashwinkumar Badanidiyuru, Robert Kleinberg, Aleksandrs Slivkins:
Bandits with Knapsacks. 207-216 - Constantinos Daskalakis, Ilias Diakonikolas, Ryan O'Donnell, Rocco A. Servedio
Learning Sums of Independent Integer Random Variables. 217-226 - Vitaly Feldman, Jan Vondrák:
Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas. 227-236 - Hamed Hatami, Shachar Lovett
Estimating the Distance from Testable Affine-Invariant Properties. 237-242 - Michael A. Forbes, Amir Shpilka
Quasipolynomial-Time Identity Testing of Non-commutative and Read-Once Oblivious Algebraic Branching Programs. 243-252 - Aleksander Madry:
Navigating Central Path with Electrical Flows: From Flows to Matchings, and Back. 253-262 - Jonah Sherman:
Nearly Maximum Flows in Nearly Linear Time. 263-269 - Sanjeev Arora, Rong Ge, Ali Kemal Sinop:
Towards a Better Approximation for Sparsest Cut? 270-279 - Vida Dujmovic, Pat Morin
Layered Separators for Queue Layouts, 3D Graph Drawing and Nonrepetitive Coloring. 280-289 - Paul Beame
Element Distinctness, Frequency Moments, and Sliding Windows. 290-299 - Alistair Sinclair, Piyush Srivastava, Yitong Yin:
Spatial Mixing and Approximation Algorithms for Graphs with Bounded Connective Constant. 300-309 - Venkatesan Guruswami, Patrick Xia:
Polar Codes: Speed of Polarization and Polynomial Gap to Capacity. 310-319 - Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir, Henning Stichtenoth:
Constant Rate PCPs for Circuit-SAT with Sublinear Query Complexity. 320-329 - Michael Viderman:
Strong LTCs with Inverse Poly-Log Rate and Constant Soundness. 330-339 - Irit Dinur
PCPs via Low-Degree Long Code and Hardness for Constrained Hypergraph Coloring. 340-349 - Siu On Chan, James R. Lee, Prasad Raghavendra, David Steurer
Approximate Constraint Satisfaction Requires Large LP Relaxations. 350-359 - Anand Louis, Prasad Raghavendra, Santosh S. Vempala:
The Complexity of Approximating Vertex Expansion. 360-369 - Parinya Chalermsook, Bundit Laekhanukit
Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses. 370-379 - Amin Coja-Oghlan, Dan Vilenchik:
Chasing the K-Colorability Threshold. 380-389 - Danny Z. Chen, Ziyun Huang
On Clustering Induced Voronoi Diagrams. 390-399 - Anna Adamaszek
Approximation Schemes for Maximum Weight Independent Set of Rectangles. 400-409 - Timothy M. Chan:
Klee's Measure Problem Made Easy. 410-419 - Dan Garber, Elad Hazan
Playing Non-linear Games with Linear Oracles. 420-428 - John C. Duchi, Michael I. Jordan
Local Privacy and Statistical Minimax Rates. 429-438 - Raef Bassily, Adam Groce, Jonathan Katz, Adam D. Smith:
Coupled-Worlds Privacy: Exploiting Adversarial Uncertainty in Statistical Data Privacy. 439-448 - Kai-Min Chung
Knowledge-Preserving Interactive Coding. 449-458 - Lior Seeman, Yaron Singer:
Adaptive Seeding in Social Networks. 459-468 - David G. Harris, Aravind Srinivasan:
The Moser-Tardos Framework with Partial Resampling. 469-478 - Russell Impagliazzo
A Satisfiability Algorithm for Sparse Depth Two Threshold Circuits. 479-488 - Serge Gaspers, Stefan Szeider
Strong Backdoors to Bounded Treewidth SAT. 489-498 - Hans L. Bodlaender
An O(c^k n) 5-Approximation Algorithm for Treewidth. 499-508 - Marek Cygan
Improved Approximation for 3-Dimensional Matching via Bounded Pathwidth Local Search. 509-518 - Natan Rubin
On Kinetic Delaunay Triangulations: A Near Quadratic Bound for Unit Speed Motions. 519-528 - Adam Marcus, Daniel A. Spielman
Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees. 529-537 - Monika Henzinger
Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization. 538-547 - Manoj Gupta, Richard Peng:
Fully Dynamic (1+ e)-Approximate Matchings. 548-557 - Mohammad Taghi Hajiaghayi, Vahid Liaghat, Debmalya Panigrahi:
Online Node-Weighted Steiner Forest and Extensions via Disk Paintings. 558-567 - Jochen Könemann, Sina Sadeghian Sadeghabad, Laura Sanità:
An LMP O(log n)-Approximation Algorithm for Node Weighted Prize Collecting Steiner Tree. 568-577 - Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi
Arithmetic Circuits: A Chasm at Depth Three. 578-587 - Ilan Komargodski, Ran Raz
Improved Average-Case Lower Bounds for DeMorgan Formula Size. 588-597 - Yuval Filmus, Toniann Pitassi, Robert Robere, Stephen A. Cook:
Average Case Lower Bounds for Monotone Switching Networks. 598-607 - Venkatesan Guruswami, Swastik Kopparty:
Explicit Subspace Designs. 608-617 - Yang Cai
Understanding Incentives: Mechanism Design Becomes Algorithm Design. 618-627 - Saeed Alaei
The Simple Economics of Approximately Optimal Auctions. 628-637 - Vittorio Bilò
The Price of Stability for Undirected Broadcast Network Design with Fair Cost Allocation Is Constant. 638-647 - Juan A. Garay, Jonathan Katz, Ueli Maurer, Björn Tackmann, Vassilis Zikas:
Rational Protocol Design: Cryptography against Incentive-Driven Adversaries. 648-657 - Hing Yin Tsang, Chung Hoi Wong, Ning Xie, Shengyu Zhang:
Fourier Sparsity, Spectral Norm, and the Log-Rank Conjecture. 658-667 - Mark Braverman, Faith Ellen, Rotem Oshman, Toniann Pitassi, Vinod Vaikuntanathan:
A Tight Bound for Set Disjointness in the Message-Passing Model. 668-677 - Mert Saglam, Gábor Tardos
On the Communication Complexity of Sparse Set Disjointness and Exists-Equal Problems. 678-687 - Gábor Braun, Sebastian Pokutta:
Common Information and Unique Disjointness. 688-697 - Yair Bartal, Lee-Ad Gottlieb
A Linear Time Approximation Scheme for Euclidean TSP. 698-706 - David B. Wilson, Uri Zwick
A Forward-Backward Single-Source Shortest Paths Algorithm. 707-716 - Sariel Har-Peled
Approximating Minimization Diagrams and Generalized Proximity Search. 717-726 - Andreas Björklund, Thore Husfeldt:
The Parity of Directed Hamiltonian Cycles. 727-735 - Andrew Drucker:
Nondeterministic Direct Product Reductions and the Success Probability of SAT Solvers. 736-745 - Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff:
Direct Products in Communication Complexity. 746-755 - David Gosset, Daniel Nagaj
Quantum 3-SAT Is QMA1-Complete. 756-765 - (Withdrawn) Three-Player Entangled XOR Games Are NP-Hard to Approximate. 766-775
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-01-13 21:38 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: