Stop the war!
Остановите войну!
for scientists:
default search action
Search dblp for Publications
export results for "toc:db/conf/focs/focs2015.bht:"
@inproceedings{DBLP:conf/focs/AbbeS15, author = {Emmanuel Abbe and Colin Sandon}, editor = {Venkatesan Guruswami}, title = {Community Detection in General Stochastic Block models: Fundamental Limits and Efficient Algorithms for Recovery}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {670--688}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.47}, doi = {10.1109/FOCS.2015.47}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/AbbeS15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/AbboudBW15, author = {Amir Abboud and Arturs Backurs and Virginia Vassilevska Williams}, editor = {Venkatesan Guruswami}, title = {Tight Hardness Results for {LCS} and Other Sequence Similarity Measures}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {59--78}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.14}, doi = {10.1109/FOCS.2015.14}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/AbboudBW15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/AbboudBW15a, author = {Amir Abboud and Arturs Backurs and Virginia Vassilevska Williams}, editor = {Venkatesan Guruswami}, title = {If the Current Clique Algorithms are Optimal, So is Valiant's Parser}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {98--117}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.16}, doi = {10.1109/FOCS.2015.16}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/AbboudBW15a.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/AggarwalDS15, author = {Divesh Aggarwal and Daniel Dadush and Noah Stephens{-}Davidowitz}, editor = {Venkatesan Guruswami}, title = {Solving the Closest Vector Problem in 2n Time - The Discrete Gaussian Strikes Again!}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {563--582}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.41}, doi = {10.1109/FOCS.2015.41}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/AggarwalDS15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/AlaeiHNPY15, author = {Saeed Alaei and Jason D. Hartline and Rad Niazadeh and Emmanouil Pountourakis and Yang Yuan}, editor = {Venkatesan Guruswami}, title = {Optimal Auctions vs. Anonymous Pricing}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {1446--1463}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.92}, doi = {10.1109/FOCS.2015.92}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/AlaeiHNPY15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/AllenOW15, author = {Sarah R. Allen and Ryan O'Donnell and David Witmer}, editor = {Venkatesan Guruswami}, title = {How to Refute a Random {CSP}}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {689--708}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.48}, doi = {10.1109/FOCS.2015.48}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/AllenOW15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/AlmanW15, author = {Josh Alman and Ryan Williams}, editor = {Venkatesan Guruswami}, title = {Probabilistic Polynomials and Hamming Nearest Neighbors}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {136--150}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.18}, doi = {10.1109/FOCS.2015.18}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/AlmanW15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/AlonNRW15, author = {Noga Alon and Noam Nisan and Ran Raz and Omri Weinstein}, editor = {Venkatesan Guruswami}, title = {Welfare Maximization with Limited Interaction}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {1499--1512}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.95}, doi = {10.1109/FOCS.2015.95}, timestamp = {Sat, 30 Sep 2023 01:00:00 +0200}, biburl = {https://dblp.org/rec/conf/focs/AlonNRW15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/AlstrupDK15, author = {Stephen Alstrup and S{\o}ren Dahlgaard and Mathias B{\ae}k Tejs Knudsen}, editor = {Venkatesan Guruswami}, title = {Optimal Induced Universal Graphs and Adjacency Labeling for Trees}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {1311--1326}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.84}, doi = {10.1109/FOCS.2015.84}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/AlstrupDK15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/AnariG15, author = {Nima Anari and Shayan Oveis Gharan}, editor = {Venkatesan Guruswami}, title = {Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric {TSP}}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {20--39}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.11}, doi = {10.1109/FOCS.2015.11}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/AnariG15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/AndersonGNR15, author = {Joseph Anderson and Navin Goyal and Anupama Nandi and Luis Rademacher}, editor = {Venkatesan Guruswami}, title = {Heavy-Tailed Independent Component Analysis}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {290--309}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.26}, doi = {10.1109/FOCS.2015.26}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/AndersonGNR15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/AsharovS15, author = {Gilad Asharov and Gil Segev}, editor = {Venkatesan Guruswami}, title = {Limits on the Power of Indistinguishability Obfuscation and Functional Encryption}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {191--209}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.21}, doi = {10.1109/FOCS.2015.21}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/AsharovS15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/AugustineP0RU15, author = {John Augustine and Gopal Pandurangan and Peter Robinson and Scott T. Roche and Eli Upfal}, editor = {Venkatesan Guruswami}, title = {Enabling Robust and Efficient Distributed Computation in Dynamic Peer-to-Peer Networks}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {350--369}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.29}, doi = {10.1109/FOCS.2015.29}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/AugustineP0RU15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/BazziFPS15, author = {Abbas Bazzi and Samuel Fiorini and Sebastian Pokutta and Ola Svensson}, editor = {Venkatesan Guruswami}, title = {No Small Linear Program Approximates Vertex Cover within a Factor 2 - e}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {1123--1142}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.73}, doi = {10.1109/FOCS.2015.73}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/BazziFPS15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/BerryCK15, author = {Dominic W. Berry and Andrew M. Childs and Robin Kothari}, editor = {Venkatesan Guruswami}, title = {Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {792--809}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.54}, doi = {10.1109/FOCS.2015.54}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/BerryCK15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/BitanskyPR15, author = {Nir Bitansky and Omer Paneth and Alon Rosen}, editor = {Venkatesan Guruswami}, title = {On the Cryptographic Hardness of Finding a Nash Equilibrium}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {1480--1498}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.94}, doi = {10.1109/FOCS.2015.94}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/BitanskyPR15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/BitanskyV15, author = {Nir Bitansky and Vinod Vaikuntanathan}, editor = {Venkatesan Guruswami}, title = {Indistinguishability Obfuscation from Functional Encryption}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {171--190}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.20}, doi = {10.1109/FOCS.2015.20}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/BitanskyV15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/BordenaveLM15, author = {Charles Bordenave and Marc Lelarge and Laurent Massouli{\'{e}}}, editor = {Venkatesan Guruswami}, title = {Non-backtracking Spectrum of Random Graphs: Community Detection and Non-regular Ramanujan Graphs}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {1347--1357}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.86}, doi = {10.1109/FOCS.2015.86}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/BordenaveLM15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/BravermanGKMT15, author = {Mark Braverman and Ankit Garg and Young Kun{-}Ko and Jieming Mao and Dave Touchette}, editor = {Venkatesan Guruswami}, title = {Near-Optimal Bounds on Bounded-Round Quantum Communication Complexity of Disjointness}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {773--791}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.53}, doi = {10.1109/FOCS.2015.53}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/BravermanGKMT15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/BrietRS15, author = {Jop Bri{\"{e}}t and Oded Regev and Rishi Saket}, editor = {Venkatesan Guruswami}, title = {Tight Hardness of the Non-commutative Grothendieck Problem}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {1108--1122}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.72}, doi = {10.1109/FOCS.2015.72}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/BrietRS15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/BringmannK15, author = {Karl Bringmann and Marvin K{\"{u}}nnemann}, editor = {Venkatesan Guruswami}, title = {Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {79--97}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.15}, doi = {10.1109/FOCS.2015.15}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/BringmannK15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/BunNSV15, author = {Mark Bun and Kobbi Nissim and Uri Stemmer and Salil P. Vadhan}, editor = {Venkatesan Guruswami}, title = {Differentially Private Release and Learning of Threshold Functions}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {634--649}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.45}, doi = {10.1109/FOCS.2015.45}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/BunNSV15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/CaiFGW15, author = {Jin{-}Yi Cai and Zhiguo Fu and Heng Guo and Tyson Williams}, editor = {Venkatesan Guruswami}, title = {A Holant Dichotomy: Is the {FKT} Algorithm Universal?}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {1259--1276}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.81}, doi = {10.1109/FOCS.2015.81}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/CaiFGW15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/ChalermsookG0MS15, author = {Parinya Chalermsook and Mayank Goswami and L{\'{a}}szl{\'{o}} Kozma and Kurt Mehlhorn and Thatchaphol Saranurak}, editor = {Venkatesan Guruswami}, title = {Pattern-Avoiding Access in Binary Search Trees}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {410--423}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.32}, doi = {10.1109/FOCS.2015.32}, timestamp = {Sat, 30 Sep 2023 01:00:00 +0200}, biburl = {https://dblp.org/rec/conf/focs/ChalermsookG0MS15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/ChanLNV15, author = {Siu Man Chan and Massimo Lauria and Jakob Nordstr{\"{o}}m and Marc Vinyals}, editor = {Venkatesan Guruswami}, title = {Hardness of Approximation in {PSPACE} and Separation Results for Pebble Games}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {466--485}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.36}, doi = {10.1109/FOCS.2015.36}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/ChanLNV15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/ChanN15, author = {Timothy M. Chan and Yakov Nekrich}, editor = {Venkatesan Guruswami}, title = {Towards an Optimal Method for Dynamic Planar Point Location}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {390--409}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.31}, doi = {10.1109/FOCS.2015.31}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/ChanN15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/ChenDOPSY15, author = {Xi Chen and Ilias Diakonikolas and Anthi Orfanou and Dimitris Paparas and Xiaorui Sun and Mihalis Yannakakis}, editor = {Venkatesan Guruswami}, title = {On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {1464--1479}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.93}, doi = {10.1109/FOCS.2015.93}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/ChenDOPSY15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/ChengCDEHT15, author = {Yu Cheng and Ho Yee Cheung and Shaddin Dughmi and Ehsan Emamjomeh{-}Zadeh and Li Han and Shang{-}Hua Teng}, editor = {Venkatesan Guruswami}, title = {Mixture Selection, Mechanism Design, and Signaling}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {1426--1445}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.91}, doi = {10.1109/FOCS.2015.91}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/ChengCDEHT15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/ChierichettiD0K15, author = {Flavio Chierichetti and Abhimanyu Das and Anirban Dasgupta and Ravi Kumar}, editor = {Venkatesan Guruswami}, title = {Approximate Modularity}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {1143--1162}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.74}, doi = {10.1109/FOCS.2015.74}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/ChierichettiD0K15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/ClarksonW15, author = {Kenneth L. Clarkson and David P. Woodruff}, editor = {Venkatesan Guruswami}, title = {Input Sparsity and Hardness for Robust Subspace Approximation}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {310--329}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.27}, doi = {10.1109/FOCS.2015.27}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/ClarksonW15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/CliffordGL15, author = {Rapha{\"{e}}l Clifford and Allan Gr{\o}nlund and Kasper Green Larsen}, editor = {Venkatesan Guruswami}, title = {New Unconditional Hardness Results for Dynamic and Online Problems}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {1089--1107}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.71}, doi = {10.1109/FOCS.2015.71}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/CliffordGL15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/Cohen15, author = {Gil Cohen}, editor = {Venkatesan Guruswami}, title = {Local Correlation Breakers and Applications to Three-Source Extractors and Mergers}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {845--862}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.57}, doi = {10.1109/FOCS.2015.57}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/Cohen15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/CurticapeanX15, author = {Radu Curticapean and Mingji Xia}, editor = {Venkatesan Guruswami}, title = {Parameterizing the Permanent: Genus, Apices, Minors, Evaluation Mod 2k}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {994--1009}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.65}, doi = {10.1109/FOCS.2015.65}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/CurticapeanX15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/DahlgaardKRT15, author = {S{\o}ren Dahlgaard and Mathias B{\ae}k Tejs Knudsen and Eva Rotenberg and Mikkel Thorup}, editor = {Venkatesan Guruswami}, title = {Hashing for Statistics over K-Partitions}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {1292--1310}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.83}, doi = {10.1109/FOCS.2015.83}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/DahlgaardKRT15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/DaskalakisKT15, author = {Constantinos Daskalakis and Gautam Kamath and Christos Tzamos}, editor = {Venkatesan Guruswami}, title = {On the Structure, Covering, and Learning of Poisson Multinomial Distributions}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {1203--1217}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.77}, doi = {10.1109/FOCS.2015.77}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/DaskalakisKT15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/De15, author = {Anindya De}, editor = {Venkatesan Guruswami}, title = {Beyond the Central Limit theorem: Asymptotic Expansions and Pseudorandomness for Combinatorial Sums}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {883--902}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.59}, doi = {10.1109/FOCS.2015.59}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/De15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/DiakonikolasKN15, author = {Ilias Diakonikolas and Daniel M. Kane and Vladimir Nikishkin}, editor = {Venkatesan Guruswami}, title = {Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {1183--1202}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.76}, doi = {10.1109/FOCS.2015.76}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/DiakonikolasKN15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/DworkSSUV15, author = {Cynthia Dwork and Adam D. Smith and Thomas Steinke and Jonathan R. Ullman and Salil P. Vadhan}, editor = {Venkatesan Guruswami}, title = {Robust Traceability from Trace Amounts}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {650--669}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.46}, doi = {10.1109/FOCS.2015.46}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/DworkSSUV15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/EdenLRS15, author = {Talya Eden and Amit Levi and Dana Ron and C. Seshadhri}, editor = {Venkatesan Guruswami}, title = {Approximately Counting Triangles in Sublinear Time}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {614--633}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.44}, doi = {10.1109/FOCS.2015.44}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/EdenLRS15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/EldanL15, author = {Ronen Eldan and James R. Lee}, editor = {Venkatesan Guruswami}, title = {Talagrand's Convolution Conjecture on Gaussian Space}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {1395--1408}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.89}, doi = {10.1109/FOCS.2015.89}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/EldanL15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/EneCKP15, author = {Alina Ene and Deeparnab Chakrabarty and Ravishankar Krishnaswamy and Debmalya Panigrahi}, editor = {Venkatesan Guruswami}, title = {Online Buy-at-Bulk Network Design}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {545--562}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.40}, doi = {10.1109/FOCS.2015.40}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/EneCKP15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/FeldmanV15, author = {Vitaly Feldman and Jan Vondr{\'{a}}k}, editor = {Venkatesan Guruswami}, title = {Tight Bounds on Low-Degree Spectral Concentration of Submodular and {XOS} Functions}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {923--942}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.61}, doi = {10.1109/FOCS.2015.61}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/FeldmanV15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/FeldmanZ15, author = {Moran Feldman and Rico Zenklusen}, editor = {Venkatesan Guruswami}, title = {The Submodular Secretary Problem Goes Linear}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {486--505}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.37}, doi = {10.1109/FOCS.2015.37}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/FeldmanZ15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/FischerLV15, author = {Eldar Fischer and Oded Lachish and Yadu Vasudev}, editor = {Venkatesan Guruswami}, title = {Trading Query Complexity for Sample-Based Testing and Multi-testing Scalability}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {1163--1182}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.75}, doi = {10.1109/FOCS.2015.75}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/FischerLV15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/Forbes15, author = {Michael A. Forbes}, editor = {Venkatesan Guruswami}, title = {Deterministic Divisibility Testing via Shifted Partial Derivatives}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {451--465}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.35}, doi = {10.1109/FOCS.2015.35}, timestamp = {Mon, 18 Sep 2023 01:00:00 +0200}, biburl = {https://dblp.org/rec/conf/focs/Forbes15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/GajarskyHLOORS15, author = {Jakub Gajarsk{\'{y}} and Petr Hlinen{\'{y}} and Daniel Lokshtanov and Jan Obdrz{\'{a}}lek and Sebastian Ordyniak and M. S. Ramanujan and Saket Saurabh}, editor = {Venkatesan Guruswami}, title = {{FO} Model Checking on Posets of Bounded Width}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {963--974}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.63}, doi = {10.1109/FOCS.2015.63}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/GajarskyHLOORS15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/GaoW15, author = {Pu Gao and Nicholas C. Wormald}, editor = {Venkatesan Guruswami}, title = {Uniform Generation of Random Regular Graphs}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {1218--1230}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.78}, doi = {10.1109/FOCS.2015.78}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/GaoW15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/GargLO15, author = {Sanjam Garg and Steve Lu and Rafail Ostrovsky}, editor = {Venkatesan Guruswami}, title = {Black-Box Garbled {RAM}}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {210--229}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.22}, doi = {10.1109/FOCS.2015.22}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/GargLO15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/GentryLSW15, author = {Craig Gentry and Allison Bishop Lewko and Amit Sahai and Brent Waters}, editor = {Venkatesan Guruswami}, title = {Indistinguishability Obfuscation from the Multilinear Subgroup Elimination Assumption}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {151--170}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.19}, doi = {10.1109/FOCS.2015.19}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/GentryLSW15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/Goos15, author = {Mika G{\"{o}}{\"{o}}s}, editor = {Venkatesan Guruswami}, title = {Lower Bounds for Clique vs. Independent Set}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {1066--1076}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.69}, doi = {10.1109/FOCS.2015.69}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/Goos15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/GoosP015, author = {Mika G{\"{o}}{\"{o}}s and Toniann Pitassi and Thomas Watson}, editor = {Venkatesan Guruswami}, title = {Deterministic Communication vs. Partition Number}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {1077--1088}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.70}, doi = {10.1109/FOCS.2015.70}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/GoosP015.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/GopalanKM15, author = {Parikshit Gopalan and Daniel M. Kane and Raghu Meka}, editor = {Venkatesan Guruswami}, title = {Pseudorandomness via the Discrete Fourier Transform}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {903--922}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.60}, doi = {10.1109/FOCS.2015.60}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/GopalanKM15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/Gottlieb15, author = {Lee{-}Ad Gottlieb}, editor = {Venkatesan Guruswami}, title = {A Light Metric Spanner}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {759--772}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.52}, doi = {10.1109/FOCS.2015.52}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/Gottlieb15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/GroheS15, author = {Martin Grohe and Pascal Schweitzer}, editor = {Venkatesan Guruswami}, title = {Isomorphism Testing for Graphs of Bounded Rank Width}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {1010--1029}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.66}, doi = {10.1109/FOCS.2015.66}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/GroheS15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/GuoHS15, author = {Alan Guo and Elad Haramaty and Madhu Sudan}, editor = {Venkatesan Guruswami}, title = {Robust Testing of Lifted Codes with Applications to Low-Degree Testing}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {825--844}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.56}, doi = {10.1109/FOCS.2015.56}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/GuoHS15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/HarveyV15, author = {Nicholas J. A. Harvey and Jan Vondr{\'{a}}k}, editor = {Venkatesan Guruswami}, title = {An Algorithmic Proof of the Lovasz Local Lemma via Resampling Oracles}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {1327--1346}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.85}, doi = {10.1109/FOCS.2015.85}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/HarveyV15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/HolmRT15, author = {Jacob Holm and Eva Rotenberg and Mikkel Thorup}, editor = {Venkatesan Guruswami}, title = {Planar Reachability in Linear Space and Constant Time}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {370--389}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.30}, doi = {10.1109/FOCS.2015.30}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/HolmRT15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/ImKKP15, author = {Sungjin Im and Nathaniel Kell and Janardhan Kulkarni and Debmalya Panigrahi}, editor = {Venkatesan Guruswami}, title = {Tight Bounds for Online Vector Scheduling}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {525--544}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.39}, doi = {10.1109/FOCS.2015.39}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/ImKKP15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/ImKM15, author = {Sungjin Im and Janardhan Kulkarni and Kamesh Munagala}, editor = {Venkatesan Guruswami}, title = {Competitive Flow Time Algorithms for Polyhedral Scheduling}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {506--524}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.38}, doi = {10.1109/FOCS.2015.38}, timestamp = {Sat, 30 Sep 2023 01:00:00 +0200}, biburl = {https://dblp.org/rec/conf/focs/ImKM15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/KantorLPP15, author = {Erez Kantor and Zvi Lotker and Merav Parter and David Peleg}, editor = {Venkatesan Guruswami}, title = {The Minimum Principle of {SINR:} {A} Useful Discretization Tool for Wireless Communication}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {330--349}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.28}, doi = {10.1109/FOCS.2015.28}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/KantorLPP15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/KhotMS15, author = {Subhash Khot and Dor Minzer and Muli Safra}, editor = {Venkatesan Guruswami}, title = {On Monotonicity Testing and Boolean Isoperimetric Type Theorems}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {52--58}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.13}, doi = {10.1109/FOCS.2015.13}, timestamp = {Sat, 30 Sep 2023 01:00:00 +0200}, biburl = {https://dblp.org/rec/conf/focs/KhotMS15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/KolmogorovKR15, author = {Vladimir Kolmogorov and Andrei A. Krokhin and Michal Rol{\'{\i}}nek}, editor = {Venkatesan Guruswami}, title = {The Complexity of General-Valued CSPs}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {1246--1258}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.80}, doi = {10.1109/FOCS.2015.80}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/KolmogorovKR15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/KopelowitzP15, author = {Tsvi Kopelowitz and Ely Porat}, editor = {Venkatesan Guruswami}, title = {Breaking the Variance: Approximating the Hamming Distance in 1/{\(\epsilon\)} Time Per Alignment}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {601--613}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.43}, doi = {10.1109/FOCS.2015.43}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/KopelowitzP15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/LeeS15, author = {Yin Tat Lee and Aaron Sidford}, editor = {Venkatesan Guruswami}, title = {Efficient Inverse Maintenance and Faster Algorithms for Linear Programming}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {230--249}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.23}, doi = {10.1109/FOCS.2015.23}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/LeeS15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/LeeS15a, author = {Yin Tat Lee and He Sun}, editor = {Venkatesan Guruswami}, title = {Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {250--269}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.24}, doi = {10.1109/FOCS.2015.24}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/LeeS15a.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/LeeSW15, author = {Yin Tat Lee and Aaron Sidford and Sam Chiu{-}wai Wong}, editor = {Venkatesan Guruswami}, title = {A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {1049--1065}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.68}, doi = {10.1109/FOCS.2015.68}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/LeeSW15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/LeverrierTZ15, author = {Anthony Leverrier and Jean{-}Pierre Tillich and Gilles Z{\'{e}}mor}, editor = {Venkatesan Guruswami}, title = {Quantum Expander Codes}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {810--824}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.55}, doi = {10.1109/FOCS.2015.55}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/LeverrierTZ15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/Li15, author = {Xin Li}, editor = {Venkatesan Guruswami}, title = {Three-Source Extractors for Polylogarithmic Min-Entropy}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {863--882}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.58}, doi = {10.1109/FOCS.2015.58}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/Li15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/LuhV15, author = {Kyle Luh and Van Vu}, editor = {Venkatesan Guruswami}, title = {Random Matrices: l1 Concentration and Dictionary Learning with Few Samples}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {1409--1425}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.90}, doi = {10.1109/FOCS.2015.90}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/LuhV15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/MakarychevMZ15, author = {Konstantin Makarychev and Yury Makarychev and Yuan Zhou}, editor = {Venkatesan Guruswami}, title = {Satisfiability of Ordering CSPs above Average is Fixed-Parameter Tractable}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {975--993}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.64}, doi = {10.1109/FOCS.2015.64}, timestamp = {Mon, 05 Feb 2024 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/MakarychevMZ15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/MarcusSS15, author = {Adam W. Marcus and Daniel A. Spielman and Nikhil Srivastava}, editor = {Venkatesan Guruswami}, title = {Interlacing Families {IV:} Bipartite Ramanujan Graphs of All Sizes}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {1358--1377}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.87}, doi = {10.1109/FOCS.2015.87}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/MarcusSS15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/MoranSWY15, author = {Shay Moran and Amir Shpilka and Avi Wigderson and Amir Yehudayoff}, editor = {Venkatesan Guruswami}, title = {Compressing and Teaching for Low VC-Dimension}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {40--51}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.12}, doi = {10.1109/FOCS.2015.12}, timestamp = {Mon, 26 Jun 2023 01:00:00 +0200}, biburl = {https://dblp.org/rec/conf/focs/MoranSWY15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/NayyeriR15, author = {Amir Nayyeri and Benjamin Raichel}, editor = {Venkatesan Guruswami}, title = {Reality Distortion: Exact and Approximate Algorithms for Embedding into the Line}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {729--747}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.50}, doi = {10.1109/FOCS.2015.50}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/NayyeriR15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/PriceS15, author = {Eric Price and Zhao Song}, editor = {Venkatesan Guruswami}, title = {A Robust Sparse Fourier Transform in the Continuous Setting}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {583--600}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.42}, doi = {10.1109/FOCS.2015.42}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/PriceS15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/Rossman15, author = {Benjamin Rossman}, editor = {Venkatesan Guruswami}, title = {The Average Sensitivity of Bounded-Depth Formulas}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {424--430}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.33}, doi = {10.1109/FOCS.2015.33}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/Rossman15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/RossmanST15, author = {Benjamin Rossman and Rocco A. Servedio and Li{-}Yang Tan}, editor = {Venkatesan Guruswami}, title = {An Average-Case Depth Hierarchy Theorem for Boolean Circuits}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {1030--1048}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.67}, doi = {10.1109/FOCS.2015.67}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/RossmanST15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/Saha15, author = {Barna Saha}, editor = {Venkatesan Guruswami}, title = {Language Edit Distance and Maximum Likelihood Parsing of Stochastic Grammars: Faster Algorithms and Connection to Fundamental Graph Problems}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {118--135}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.17}, doi = {10.1109/FOCS.2015.17}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/Saha15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/SchulmanSS15, author = {Leonard J. Schulman and Alistair Sinclair and Piyush Srivastava}, editor = {Venkatesan Guruswami}, title = {Symbolic Integration and the Complexity of Computing Averages}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {1231--1245}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.79}, doi = {10.1109/FOCS.2015.79}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/SchulmanSS15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/SeidlMK15, author = {Helmut Seidl and Sebastian Maneth and Gregor Kemper}, editor = {Venkatesan Guruswami}, title = {Equivalence of Deterministic Top-Down Tree-to-String Transducers is Decidable}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {943--962}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.62}, doi = {10.1109/FOCS.2015.62}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/SeidlMK15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/SharirS15, author = {Micha Sharir and Noam Solomon}, editor = {Venkatesan Guruswami}, title = {Incidences between Points and Lines in {R4}}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {1378--1394}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.88}, doi = {10.1109/FOCS.2015.88}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/SharirS15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/ShepherdVW15, author = {F. Bruce Shepherd and Adrian Vetta and Gordon T. Wilfong}, editor = {Venkatesan Guruswami}, title = {Polylogarithmic Approximations for the Capacitated Single-Sink Confluent Flow Problem}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {748--758}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.51}, doi = {10.1109/FOCS.2015.51}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/ShepherdVW15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/Sherstov15, author = {Alexander A. Sherstov}, editor = {Venkatesan Guruswami}, title = {The Power of Asymmetry in Constant-Depth Circuits}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {431--450}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.34}, doi = {10.1109/FOCS.2015.34}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/Sherstov15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/SunL15, author = {Ruoyu Sun and Zhi{-}Quan Luo}, editor = {Venkatesan Guruswami}, title = {Guaranteed Matrix Completion via Nonconvex Factorization}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {270--289}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.25}, doi = {10.1109/FOCS.2015.25}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/SunL15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/Svensson15, author = {Ola Svensson}, editor = {Venkatesan Guruswami}, title = {Approximating {ATSP} by Relaxing Connectivity}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {1--19}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.10}, doi = {10.1109/FOCS.2015.10}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/Svensson15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/Thorup15, author = {Mikkel Thorup}, editor = {Venkatesan Guruswami}, title = {Sample (x) = (a*x{\textless}=t) is a Distinguisher with Probability 1/8}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {1277--1291}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.82}, doi = {10.1109/FOCS.2015.82}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/Thorup15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@inproceedings{DBLP:conf/focs/Zenklusen15, author = {Rico Zenklusen}, editor = {Venkatesan Guruswami}, title = {An O(1)-Approximation for Minimum Spanning Tree Interdiction}, booktitle = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, pages = {709--728}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://doi.org/10.1109/FOCS.2015.49}, doi = {10.1109/FOCS.2015.49}, timestamp = {Thu, 23 Mar 2023 00:00:00 +0100}, biburl = {https://dblp.org/rec/conf/focs/Zenklusen15.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
@proceedings{DBLP:conf/focs/2015, editor = {Venkatesan Guruswami}, title = {{IEEE} 56th Annual Symposium on Foundations of Computer Science, {FOCS} 2015, Berkeley, CA, USA, 17-20 October, 2015}, publisher = {{IEEE} Computer Society}, year = {2015}, url = {https://ieeexplore.ieee.org/xpl/conhome/7352273/proceeding}, isbn = {978-1-4673-8191-8}, timestamp = {Wed, 16 Oct 2019 01:00:00 +0200}, biburl = {https://dblp.org/rec/conf/focs/2015.bib}, bibsource = {dblp computer science bibliography, https://dblp.org} }
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.