default search action
56th FOCS 2015: Berkeley, CA, USA
- Venkatesan Guruswami:
IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015. IEEE Computer Society 2015, ISBN 978-1-4673-8191-8 - Ola Svensson:
Approximating ATSP by Relaxing Connectivity. 1-19 - Nima Anari
, Shayan Oveis Gharan:
Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric TSP. 20-39 - Shay Moran, Amir Shpilka
Compressing and Teaching for Low VC-Dimension. 40-51 - Subhash Khot, Dor Minzer, Muli Safra
On Monotonicity Testing and Boolean Isoperimetric Type Theorems. 52-58 - Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams:
Tight Hardness Results for LCS and Other Sequence Similarity Measures. 59-78 - Karl Bringmann, Marvin Künnemann:
Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping. 79-97 - Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams:
If the Current Clique Algorithms are Optimal, So is Valiant's Parser. 98-117 - Barna Saha:
Language Edit Distance and Maximum Likelihood Parsing of Stochastic Grammars: Faster Algorithms and Connection to Fundamental Graph Problems. 118-135 - Josh Alman, Ryan Williams
Probabilistic Polynomials and Hamming Nearest Neighbors. 136-150 - Craig Gentry, Allison Bishop Lewko, Amit Sahai, Brent Waters:
Indistinguishability Obfuscation from the Multilinear Subgroup Elimination Assumption. 151-170 - Nir Bitansky, Vinod Vaikuntanathan:
Indistinguishability Obfuscation from Functional Encryption. 171-190 - Gilad Asharov
Limits on the Power of Indistinguishability Obfuscation and Functional Encryption. 191-209 - Sanjam Garg
Black-Box Garbled RAM. 210-229 - Yin Tat Lee, Aaron Sidford:
Efficient Inverse Maintenance and Faster Algorithms for Linear Programming. 230-249 - Yin Tat Lee, He Sun:
Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time. 250-269 - Ruoyu Sun, Zhi-Quan Luo:
Guaranteed Matrix Completion via Nonconvex Factorization. 270-289 - Joseph Anderson, Navin Goyal, Anupama Nandi, Luis Rademacher
Heavy-Tailed Independent Component Analysis. 290-309 - Kenneth L. Clarkson, David P. Woodruff:
Input Sparsity and Hardness for Robust Subspace Approximation. 310-329 - Erez Kantor, Zvi Lotker, Merav Parter, David Peleg:
The Minimum Principle of SINR: A Useful Discretization Tool for Wireless Communication. 330-349 - John Augustine, Gopal Pandurangan
Enabling Robust and Efficient Distributed Computation in Dynamic Peer-to-Peer Networks. 350-369 - Jacob Holm
Planar Reachability in Linear Space and Constant Time. 370-389 - Timothy M. Chan, Yakov Nekrich
Towards an Optimal Method for Dynamic Planar Point Location. 390-409 - Parinya Chalermsook, Mayank Goswami, László Kozma
Pattern-Avoiding Access in Binary Search Trees. 410-423 - Benjamin Rossman:
The Average Sensitivity of Bounded-Depth Formulas. 424-430 - Alexander A. Sherstov:
The Power of Asymmetry in Constant-Depth Circuits. 431-450 - Michael A. Forbes:
Deterministic Divisibility Testing via Shifted Partial Derivatives. 451-465 - Siu Man Chan, Massimo Lauria
Hardness of Approximation in PSPACE and Separation Results for Pebble Games. 466-485 - Moran Feldman
The Submodular Secretary Problem Goes Linear. 486-505 - Sungjin Im, Janardhan Kulkarni, Kamesh Munagala
Competitive Flow Time Algorithms for Polyhedral Scheduling. 506-524 - Sungjin Im, Nathaniel Kell, Janardhan Kulkarni, Debmalya Panigrahi:
Tight Bounds for Online Vector Scheduling. 525-544 - Alina Ene, Deeparnab Chakrabarty, Ravishankar Krishnaswamy, Debmalya Panigrahi:
Online Buy-at-Bulk Network Design. 545-562 - Divesh Aggarwal, Daniel Dadush, Noah Stephens-Davidowitz:
Solving the Closest Vector Problem in 2^n Time - The Discrete Gaussian Strikes Again! 563-582 - Eric Price, Zhao Song:
A Robust Sparse Fourier Transform in the Continuous Setting. 583-600 - Tsvi Kopelowitz, Ely Porat:
Breaking the Variance: Approximating the Hamming Distance in 1/ε Time Per Alignment. 601-613 - Talya Eden, Amit Levi, Dana Ron
Approximately Counting Triangles in Sublinear Time. 614-633 - Mark Bun, Kobbi Nissim
Differentially Private Release and Learning of Threshold Functions. 634-649 - Cynthia Dwork, Adam D. Smith, Thomas Steinke, Jonathan R. Ullman, Salil P. Vadhan:
Robust Traceability from Trace Amounts. 650-669 - Emmanuel Abbe, Colin Sandon:
Community Detection in General Stochastic Block models: Fundamental Limits and Efficient Algorithms for Recovery. 670-688 - Sarah R. Allen, Ryan O'Donnell, David Witmer:
How to Refute a Random CSP. 689-708 - Rico Zenklusen:
An O(1)-Approximation for Minimum Spanning Tree Interdiction. 709-728 - Amir Nayyeri, Benjamin Raichel:
Reality Distortion: Exact and Approximate Algorithms for Embedding into the Line. 729-747 - F. Bruce Shepherd, Adrian Vetta, Gordon T. Wilfong:
Polylogarithmic Approximations for the Capacitated Single-Sink Confluent Flow Problem. 748-758 - Lee-Ad Gottlieb
A Light Metric Spanner. 759-772 - Mark Braverman, Ankit Garg, Young Kun-Ko, Jieming Mao, Dave Touchette:
Near-Optimal Bounds on Bounded-Round Quantum Communication Complexity of Disjointness. 773-791 - Dominic W. Berry
Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters. 792-809 - Anthony Leverrier
Quantum Expander Codes. 810-824 - Alan Guo, Elad Haramaty, Madhu Sudan:
Robust Testing of Lifted Codes with Applications to Low-Degree Testing. 825-844 - Gil Cohen:
Local Correlation Breakers and Applications to Three-Source Extractors and Mergers. 845-862 - Xin Li:
Three-Source Extractors for Polylogarithmic Min-Entropy. 863-882 - Anindya De:
Beyond the Central Limit theorem: Asymptotic Expansions and Pseudorandomness for Combinatorial Sums. 883-902 - Parikshit Gopalan, Daniel M. Kane, Raghu Meka:
Pseudorandomness via the Discrete Fourier Transform. 903-922 - Vitaly Feldman, Jan Vondrák:
Tight Bounds on Low-Degree Spectral Concentration of Submodular and XOS Functions. 923-942 - Helmut Seidl, Sebastian Maneth, Gregor Kemper:
Equivalence of Deterministic Top-Down Tree-to-String Transducers is Decidable. 943-962 - Jakub Gajarský, Petr Hlinený
FO Model Checking on Posets of Bounded Width. 963-974 - Konstantin Makarychev, Yury Makarychev, Yuan Zhou
Satisfiability of Ordering CSPs above Average is Fixed-Parameter Tractable. 975-993 - Radu Curticapean, Mingji Xia:
Parameterizing the Permanent: Genus, Apices, Minors, Evaluation Mod 2k. 994-1009 - Martin Grohe
Isomorphism Testing for Graphs of Bounded Rank Width. 1010-1029 - Benjamin Rossman, Rocco A. Servedio
An Average-Case Depth Hierarchy Theorem for Boolean Circuits. 1030-1048 - Yin Tat Lee, Aaron Sidford, Sam Chiu-wai Wong:
A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization. 1049-1065 - Mika Göös:
Lower Bounds for Clique vs. Independent Set. 1066-1076 - Mika Göös, Toniann Pitassi, Thomas Watson:
Deterministic Communication vs. Partition Number. 1077-1088 - Raphaël Clifford, Allan Grønlund, Kasper Green Larsen:
New Unconditional Hardness Results for Dynamic and Online Problems. 1089-1107 - Jop Briët, Oded Regev, Rishi Saket:
Tight Hardness of the Non-commutative Grothendieck Problem. 1108-1122 - Abbas Bazzi, Samuel Fiorini, Sebastian Pokutta, Ola Svensson:
No Small Linear Program Approximates Vertex Cover within a Factor 2 - e. 1123-1142 - Flavio Chierichetti, Abhimanyu Das, Anirban Dasgupta
Approximate Modularity. 1143-1162 - Eldar Fischer, Oded Lachish
Trading Query Complexity for Sample-Based Testing and Multi-testing Scalability. 1163-1182 - Ilias Diakonikolas, Daniel M. Kane, Vladimir Nikishkin
Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions. 1183-1202 - Constantinos Daskalakis, Gautam Kamath
On the Structure, Covering, and Learning of Poisson Multinomial Distributions. 1203-1217 - Pu Gao, Nicholas C. Wormald:
Uniform Generation of Random Regular Graphs. 1218-1230 - Leonard J. Schulman
Symbolic Integration and the Complexity of Computing Averages. 1231-1245 - Vladimir Kolmogorov, Andrei A. Krokhin
The Complexity of General-Valued CSPs. 1246-1258 - Jin-Yi Cai, Zhiguo Fu, Heng Guo, Tyson Williams:
A Holant Dichotomy: Is the FKT Algorithm Universal? 1259-1276 - Mikkel Thorup
Sample (x) = (a*x<=t) is a Distinguisher with Probability 1/8. 1277-1291 - Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Eva Rotenberg
Hashing for Statistics over K-Partitions. 1292-1310 - Stephen Alstrup, Søren Dahlgaard, Mathias Bæk Tejs Knudsen:
Optimal Induced Universal Graphs and Adjacency Labeling for Trees. 1311-1326 - Nicholas J. A. Harvey, Jan Vondrák:
An Algorithmic Proof of the Lovasz Local Lemma via Resampling Oracles. 1327-1346 - Charles Bordenave, Marc Lelarge, Laurent Massoulié:
Non-backtracking Spectrum of Random Graphs: Community Detection and Non-regular Ramanujan Graphs. 1347-1357 - Adam W. Marcus, Daniel A. Spielman
Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes. 1358-1377 - Micha Sharir, Noam Solomon:
Incidences between Points and Lines in R^4. 1378-1394 - Ronen Eldan, James R. Lee:
Talagrand's Convolution Conjecture on Gaussian Space. 1395-1408 - Kyle Luh, Van Vu:
Random Matrices: l1 Concentration and Dictionary Learning with Few Samples. 1409-1425 - Yu Cheng
Mixture Selection, Mechanism Design, and Signaling. 1426-1445 - Saeed Alaei
Optimal Auctions vs. Anonymous Pricing. 1446-1463 - Xi Chen, Ilias Diakonikolas, Anthi Orfanou, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis:
On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms. 1464-1479 - Nir Bitansky, Omer Paneth, Alon Rosen:
On the Cryptographic Hardness of Finding a Nash Equilibrium. 1480-1498 - Noga Alon, Noam Nisan
Welfare Maximization with Limited Interaction. 1499-1512
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 2024-12-26 01:01 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: