Google
Google Scholar
MS Academic
CiteSeerX
CORE
Semantic Scholar56th 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- Nima Anari, Shayan Oveis Gharan:
Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric TSP. 20-39 - Shay Moran, Amir Shpilka, Avi Wigderson, Amir Yehudayoff:
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 - 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, Gil Segev:
Limits on the Power of Indistinguishability Obfuscation and Functional Encryption. 191-209 - 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 - 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, Peter Robinson, Scott T. Roche, Eli Upfal:
Enabling Robust and Efficient Distributed Computation in Dynamic Peer-to-Peer Networks. 350-369 - Jacob Holm, Eva Rotenberg, Mikkel Thorup:
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, Kurt Mehlhorn, Thatchaphol Saranurak:
Pattern-Avoiding Access in Binary Search Trees. 410-423 - Siu Man Chan, Massimo Lauria, Jakob Nordström, Marc Vinyals:
Hardness of Approximation in PSPACE and Separation Results for Pebble Games. 466-485 - 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 - Tsvi Kopelowitz, Ely Porat:
Breaking the Variance: Approximating the Hamming Distance in 1/ε Time Per Alignment. 601-613 - Talya Eden, Amit Levi, Dana Ron, C. Seshadhri:
Approximately Counting Triangles in Sublinear Time. 614-633 - Mark Bun, Kobbi Nissim, Uri Stemmer, Salil P. Vadhan:
Differentially Private Release and Learning of Threshold Functions. 634-649 - Cynthia Dwork, Adam D. Smith, Thomas Steinke, Jonathan 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 - 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 - 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, Andrew M. Childs, Robin Kothari:
Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters. 792-809 - 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 - 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ý, Daniel Lokshtanov, Jan Obdrzálek, Sebastian Ordyniak, M. S. Ramanujan, Saket Saurabh:
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 - Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan:
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, 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 - Eldar Fischer, Oded Lachish, Yadu Vasudev:
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, Christos Tzamos:
On the Structure, Covering, and Learning of Poisson Multinomial Distributions. 1203-1217 - Leonard J. Schulman, Alistair Sinclair, Piyush Srivastava:
Symbolic Integration and the Complexity of Computing Averages. 1231-1245 - Vladimir Kolmogorov, Andrei A. Krokhin, Michal Rolinek:
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 - Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Eva Rotenberg, Mikkel Thorup:
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, Nikhil Srivastava:
Interlacing Families IV: Bipartite Ramanujan Graphs of All Sizes. 1358-1377 - Yu Cheng, Ho Yee Cheung, Shaddin Dughmi, Ehsan Emamjomeh-Zadeh, Li Han, Shang-Hua Teng:
Mixture Selection, Mechanism Design, and Signaling. 1426-1445 - Saeed Alaei, Jason D. Hartline, Rad Niazadeh, Emmanouil Pountourakis, Yang Yuan:
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, Ran Raz, Omri Weinstein:
Welfare Maximization with Limited Interaction. 1499-1512
maintained by 
at 
at 
last updated on 2018-12-16 21:27 CET by the dblp team
data released under the ODC-BY 1.0 license
see also: Terms of Use | Privacy Policy | Imprint