default search action
55th FOCS 2014: Philadelphia, PA, USA
- 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014. IEEE Computer Society 2014, ISBN 978-1-4799-6517-5
- Per Austrin, Johan Håstad
, Venkatesan Guruswami:
(2 + epsilon)-Sat Is NP-Hard. 1-10 - Constantinos Daskalakis, Qinxuan Pan:
A Counter-example to Karlin's Strong Conjecture for Fictitious Play. 11-20 - Moshe Babaioff, Nicole Immorlica, Brendan Lucier, S. Matthew Weinberg
A Simple and Approximately Optimal Mechanism for an Additive Buyer. 21-30 - Umang Bhaskar, Katrina Ligett
Achieving Target Equilibria in Network Routing Games without Knowing the Latency Functions. 31-40 - Vipul Goyal, Silas Richelson, Alon Rosen, Margarita Vald:
An Algebraic Approach to Non-malleability. 41-50 - Gregory Valiant, Paul Valiant:
An Automatic Inequality Prover and Instance Optimal Identity Testing. 51-60 - Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan
An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas. 61-70 - Tim Roughgarden:
Barriers to Near-Optimal Equilibria. 71-80 - Itai Benjamini, Gil Cohen, Igor Shinkar:
Bi-Lipschitz Bijection between the Boolean Cube and the Hamming Ball. 81-89 - Leonid Gurvits, Alex Samorodnitsky:
Bounds on the Permanent and Some Applications. 90-99 - Uriel Feige, Tomer Koren, Moshe Tennenholtz:
Chasing Ghosts: Competing with Stateful Policies. 100-109 - Joshua A. Grochow, Toniann Pitassi:
Circuit Complexity, Proof Complexity, and Polynomial Identity Testing. 110-119 - Toby S. Cubitt
Complexity Classification of Local Hamiltonian Problems. 120-129 - Radu Curticapean, Dániel Marx:
Complexity of Counting Subgraphs: Only the Boundedness of the Vertex-Cover Number Counts. 130-139 - Thomas Rothvoß:
Constructive Discrepancy Minimization for Convex Sets. 140-145 - Monika Henzinger
Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time. 146-155 - George Barmpalias
Digital Morphogenesis via Schelling Segregation. 156-165 - Mihai Patrascu, Mikkel Thorup
Dynamic Integer Sets with Optimal Rank, Select, and Predecessor Search. 166-175 - Anat Ganor, Gillat Kol, Ran Raz
Exponential Separation of Information and Communication. 176-185 - Daniel Lokshtanov, Marcin Pilipczuk
Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth. 186-195 - Tobias Christiani, Rasmus Pagh:
Generating k-Independent Variables in Constant Time. 196-205 - Subhash Khot, Rishi Saket:
Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with exp(log^{Omega(1)} n) Colors. 206-215 - François Le Gall:
Improved Quantum Algorithm for Triangle Finding via Combinatorial Arguments. 216-225 - Bernhard Haeupler
Interactive Channel Capacity Revisited. 226-235 - Mark Braverman, Klim Efremenko
List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise. 236-245 - Dorit Aharonov, Aram W. Harrow
Local Tests of Global Entanglement and a Counterexample to the Generalized Area Law. 246-255 - Hyung-Chan An, Mohit Singh, Ola Svensson:
LP-Based Algorithms for Capacitated Facility Location. 256-265 - Nima Anari
Mechanism Design for Crowdsourcing: An Optimal 1-1/e Competitive Budget-Feasible Mechanism for Large Markets. 266-275 - Marcin Pilipczuk
Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs. 276-285 - Xi Chen, Rocco A. Servedio
New Algorithms and Lower Bounds for Monotonicity Testing. 286-295 - Gilles Brassard, Ashwin Nayak, Alain Tapp, Dave Touchette, Falk Unger:
Noisy Interactive Quantum Communication. 296-305 - Eshan Chattopadhyay, David Zuckerman:
Non-malleable Codes against Constant Split-State Tampering. 306-315 - Sian-Jheng Lin, Wei-Ho Chung, Yunghsiang S. Han:
Novel Polynomial Basis and Its Application to Reed-Solomon Erasure Codes. 316-325 - Oded Lachish
O(log log Rank) Competitive Ratio for the Matroid Secretary Problem. 326-335 - Oded Goldreich
On Learning and Testing Dynamic Environments. 336-343 - Yuan Li, Alexander A. Razborov, Benjamin Rossman:
On the AC0 Complexity of Subgraph Isomorphism. 344-353 - Shaddin Dughmi:
On the Hardness of Signaling. 354-363 - Mrinal Kumar, Shubhangi Saraf:
On the Power of Homogeneous Depth 4 Arithmetic Circuits. 364-373 - Ilan Komargodski, Tal Moran, Moni Naor, Rafael Pass
One-Way Functions and (Im)Perfect Obfuscation. 374-383 - Bartlomiej Bosek
Online Bipartite Matching in Offline Time. 384-393 - Mohsen Ghaffari, Bernhard Haeupler
Optimal Error Rates for Interactive Coding II: Efficiency and List Decoding. 394-403 - Craig Gentry, Shai Halevi, Mariana Raykova, Daniel Wichs:
Outsourcing Private RAM Computation. 404-413 - Dana Moshkovitz:
Parallel Repetition from Fortification. 414-423 - Yin Tat Lee, Aaron Sidford:
Path Finding Methods for Linear Programming: Solving Linear Programs in Õ(vrank) Iterations and Faster Algorithms for Maximum Flow. 424-433 - Amir Abboud, Virginia Vassilevska Williams:
Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems. 434-443 - Parinya Chalermsook, Bundit Laekhanukit
Pre-reduction Graph Products: Hardnesses of Properly Learning DFAs and Approximating EDP on DAGs. 444-453 - Moritz Hardt, Jonathan R. Ullman:
Preventing False Discovery in Interactive Data Analysis Is Hard. 454-463 - Raef Bassily, Adam D. Smith, Abhradeep Thakurta:
Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds. 464-473 - Andris Ambainis, Ansis Rosmanis, Dominique Unruh
Quantum Attacks on Classical Proof Systems: The Hardness of Quantum Rewinding. 474-483 - Tali Kaufman, David Kazhdan, Alexander Lubotzky
Ramanujan Complexes and Bounded Degree Topological Expanders. 484-493 - Dimitris Achlioptas, Fotis Iliopoulos:
Random Walks That Find Perfect Objects and the Lovasz Local Lemma. 494-503 - George Giakkoupis, Philipp Woelfel:
Randomized Mutual Exclusion with Constant Amortized RMR Complexity on the DSM. 504-513 - Piotr Indyk, Michael Kapralov
Sample-Optimal Fourier Sampling in Any Constant Dimension. 514-523 - Adi Livnat, Christos H. Papadimitriou, Aviad Rubinstein, Gregory Valiant, Andrew Wan:
Satisfiability and Evolution. 524-530 - Sungjin Im, Janardhan Kulkarni, Kamesh Munagala, Kirk Pruhs:
SelfishMigrate: A Scalable Algorithm for Non-clairvoyantly Scheduling Heterogeneous Processors. 531-540 - Nabil H. Mustafa
Settling the APX-Hardness Status for Geometric Set Cover. 541-550 - Avishay Tal:
Shrinkage of De Morgan Formulae by Spectral Techniques. 551-560 - Michael Kapralov
Single Pass Spectral Sparsification in Dynamic Streams. 561-570 - Konstantin Makarychev, Maxim Sviridenko:
Solving Optimization Problems with Diseconomies of Scale via Decoupling. 571-580 - Amirali Abdullah, Alexandr Andoni, Ravindran Kannan, Robert Krauthgamer
Spectral Approaches to Nearest Neighbor Search. 581-590 - Zengfeng Huang
The Communication Complexity of Distributed epsilon-Approximations. 591-600 - Jin-Yi Cai, Heng Guo, Tyson Williams:
The Complexity of Counting Edge Colorings and a Dichotomy for Some Higher Domain Holant Problems. 601-610 - Barna Saha:
The Dyck Language Edit Distance Problem in Near-Linear Time. 611-620 - Allan Grønlund Jørgensen, Seth Pettie:
Threesomes, Degenerates, and Love Triangles. 621-630 - Arkadev Chattopadhyay, Jaikumar Radhakrishnan, Atri Rudra:
Topology Matters in Communication. 631-640 - Ilario Bonacina
Total Space in Resolution. 641-650 - Moritz Hardt:
Understanding Alternating Minimization for Matrix Completion. 651-660 - Karl Bringmann:
Why Walking the Dog Takes Time: Frechet Distance Has No Strongly Subquadratic Algorithms Unless SETH Fails. 661-670
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-26 23:57 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: