Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
1 | Joseph Anderson, Navin Goyal, Anupama Nandi, Luis Rademacher |
Heavy-Tailed Independent Component Analysis. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Constantinos Daskalakis, Gautam Kamath 0001, Christos Tzamos |
On the Structure, Covering, and Learning of Poisson Multinomial Distributions. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Xin Li 0006 |
Three-Source Extractors for Polylogarithmic Min-Entropy. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Kenneth L. Clarkson, David P. Woodruff |
Input Sparsity and Hardness for Robust Subspace Approximation. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Rico Zenklusen |
An O(1)-Approximation for Minimum Spanning Tree Interdiction. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Mark Braverman, Ankit Garg, Young Kun-Ko, Jieming Mao, Dave Touchette |
Near-Optimal Bounds on Bounded-Round Quantum Communication Complexity of Disjointness. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Sanjam Garg, Steve Lu 0001, Rafail Ostrovsky |
Black-Box Garbled RAM. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Barna Saha |
Language Edit Distance and Maximum Likelihood Parsing of Stochastic Grammars: Faster Algorithms and Connection to Fundamental Graph Problems. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Parinya Chalermsook, Mayank Goswami 0001, László Kozma 0002, Kurt Mehlhorn, Thatchaphol Saranurak |
Pattern-Avoiding Access in Binary Search Trees. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Konstantin Makarychev, Yury Makarychev, Yuan Zhou 0007 |
Satisfiability of Ordering CSPs above Average is Fixed-Parameter Tractable. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Gil Cohen |
Local Correlation Breakers and Applications to Three-Source Extractors and Mergers. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Yin Tat Lee, Aaron Sidford, Sam Chiu-wai Wong |
A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Martin Grohe, Pascal Schweitzer |
Isomorphism Testing for Graphs of Bounded Rank Width. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams |
Tight Hardness Results for LCS and Other Sequence Similarity Measures. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Tsvi Kopelowitz, Ely Porat |
Breaking the Variance: Approximating the Hamming Distance in 1/ε Time Per Alignment. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Anindya De |
Beyond the Central Limit theorem: Asymptotic Expansions and Pseudorandomness for Combinatorial Sums. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Subhash Khot, Dor Minzer, Muli Safra |
On Monotonicity Testing and Boolean Isoperimetric Type Theorems. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Eric Price 0001, Zhao Song 0002 |
A Robust Sparse Fourier Transform in the Continuous Setting. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
1 | John Augustine, Gopal Pandurangan, Peter Robinson 0002, Scott T. Roche, Eli Upfal |
Enabling Robust and Efficient Distributed Computation in Dynamic Peer-to-Peer Networks. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Xi Chen 0001, Ilias Diakonikolas, Anthi Orfanou, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis |
On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Mika Göös |
Lower Bounds for Clique vs. Independent Set. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Craig Gentry, Allison Bishop Lewko, Amit Sahai, Brent Waters |
Indistinguishability Obfuscation from the Multilinear Subgroup Elimination Assumption. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Siu Man Chan, Massimo Lauria, Jakob Nordström, Marc Vinyals |
Hardness of Approximation in PSPACE and Separation Results for Pebble Games. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Jop Briët, Oded Regev 0001, Rishi Saket |
Tight Hardness of the Non-commutative Grothendieck Problem. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Erez Kantor, Zvi Lotker, Merav Parter, David Peleg |
The Minimum Principle of SINR: A Useful Discretization Tool for Wireless Communication. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Venkatesan Guruswami (eds.) |
IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015 |
FOCS |
2015 |
DBLP BibTeX RDF |
|
1 | Anthony Leverrier, Jean-Pierre Tillich, Gilles Zémor |
Quantum Expander Codes. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Ola Svensson |
Approximating ATSP by Relaxing Connectivity. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Eldar Fischer, Oded Lachish, Yadu Vasudev |
Trading Query Complexity for Sample-Based Testing and Multi-testing Scalability. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Radu Curticapean, Mingji Xia |
Parameterizing the Permanent: Genus, Apices, Minors, Evaluation Mod 2k. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Emmanuel Abbe, Colin Sandon |
Community Detection in General Stochastic Block models: Fundamental Limits and Efficient Algorithms for Recovery. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Ronen Eldan, James R. Lee |
Talagrand's Convolution Conjecture on Gaussian Space. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Kyle Luh, Van Vu |
Random Matrices: l1 Concentration and Dictionary Learning with Few Samples. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Sungjin Im, Nathaniel Kell, Janardhan Kulkarni, Debmalya Panigrahi |
Tight Bounds for Online Vector Scheduling. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Alan Guo, Elad Haramaty, Madhu Sudan 0001 |
Robust Testing of Lifted Codes with Applications to Low-Degree Testing. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Flavio Chierichetti, Abhimanyu Das, Anirban Dasgupta 0001, Ravi Kumar 0001 |
Approximate Modularity. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Helmut Seidl, Sebastian Maneth, Gregor Kemper |
Equivalence of Deterministic Top-Down Tree-to-String Transducers is Decidable. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Yu Cheng 0002, Ho Yee Cheung, Shaddin Dughmi, Ehsan Emamjomeh-Zadeh, Li Han, Shang-Hua Teng |
Mixture Selection, Mechanism Design, and Signaling. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Ilias Diakonikolas, Daniel M. Kane, Vladimir Nikishkin |
Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
1 | F. Bruce Shepherd, Adrian Vetta, Gordon T. Wilfong |
Polylogarithmic Approximations for the Capacitated Single-Sink Confluent Flow Problem. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Stephen Alstrup, Søren Dahlgaard, Mathias Bæk Tejs Knudsen |
Optimal Induced Universal Graphs and Adjacency Labeling for Trees. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Alexander A. Sherstov |
The Power of Asymmetry in Constant-Depth Circuits. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Noga Alon, Noam Nisan, Ran Raz, Omri Weinstein |
Welfare Maximization with Limited Interaction. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Mark Bun, Kobbi Nissim, Uri Stemmer, Salil P. Vadhan |
Differentially Private Release and Learning of Threshold Functions. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Yin Tat Lee, He Sun 0001 |
Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Abbas Bazzi, Samuel Fiorini, Sebastian Pokutta, Ola Svensson |
No Small Linear Program Approximates Vertex Cover within a Factor 2 - e. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Yin Tat Lee, Aaron Sidford |
Efficient Inverse Maintenance and Faster Algorithms for Linear Programming. |
FOCS |
2015 |
DBLP DOI BibTeX RDF |
|
1 | Uriel Feige, Tomer Koren, Moshe Tennenholtz |
Chasing Ghosts: Competing with Stateful Policies. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Constantinos Daskalakis, Qinxuan Pan |
A Counter-example to Karlin's Strong Conjecture for Fictitious Play. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Adi Livnat, Christos H. Papadimitriou, Aviad Rubinstein, Gregory Valiant, Andrew Wan |
Satisfiability and Evolution. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Subhash Khot, Rishi Saket |
Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with exp(log^{Omega(1)} n) Colors. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | George Barmpalias, Richard Elwes, Andy Lewis-Pye |
Digital Morphogenesis via Schelling Segregation. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Dorit Aharonov, Aram W. Harrow, Zeph Landau, Daniel Nagaj, Mario Szegedy, Umesh V. Vazirani |
Local Tests of Global Entanglement and a Counterexample to the Generalized Area Law. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Nima Anari, Gagan Goel, Afshin Nikzad |
Mechanism Design for Crowdsourcing: An Optimal 1-1/e Competitive Budget-Feasible Mechanism for Large Markets. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Moritz Hardt |
Understanding Alternating Minimization for Matrix Completion. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Umang Bhaskar, Katrina Ligett, Leonard J. Schulman, Chaitanya Swamy |
Achieving Target Equilibria in Network Routing Games without Knowing the Latency Functions. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Toby S. Cubitt, Ashley Montanaro |
Complexity Classification of Local Hamiltonian Problems. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Oded Lachish |
O(log log Rank) Competitive Ratio for the Matroid Secretary Problem. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai |
Pre-reduction Graph Products: Hardnesses of Properly Learning DFAs and Approximating EDP on DAGs. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Anat Ganor, Gillat Kol, Ran Raz |
Exponential Separation of Information and Communication. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Dana Moshkovitz |
Parallel Repetition from Fortification. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Xi Chen 0001, Rocco A. Servedio, Li-Yang Tan |
New Algorithms and Lower Bounds for Monotonicity Testing. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Dimitris Achlioptas, Fotis Iliopoulos |
Random Walks That Find Perfect Objects and the Lovasz Local Lemma. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Tali Kaufman, David Kazhdan, Alexander Lubotzky |
Ramanujan Complexes and Bounded Degree Topological Expanders. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Karl Bringmann |
Why Walking the Dog Takes Time: Frechet Distance Has No Strongly Subquadratic Algorithms Unless SETH Fails. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Raef Bassily, Adam D. Smith, Abhradeep Thakurta |
Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Eshan Chattopadhyay, David Zuckerman |
Non-malleable Codes against Constant Split-State Tampering. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Ilario Bonacina, Nicola Galesi, Neil Thapen |
Total Space in Resolution. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Neeraj Kayal, Nutan Limaye, Chandan Saha 0001, Srikanth Srinivasan 0001 |
An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Tim Roughgarden |
Barriers to Near-Optimal Equilibria. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Marcin Pilipczuk, Michal Pilipczuk, Piotr Sankowski, Erik Jan van Leeuwen |
Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Sungjin Im, Janardhan Kulkarni, Kamesh Munagala, Kirk Pruhs |
SelfishMigrate: A Scalable Algorithm for Non-clairvoyantly Scheduling Heterogeneous Processors. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Piotr Indyk, Michael Kapralov |
Sample-Optimal Fourier Sampling in Any Constant Dimension. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco, Aaron Sidford |
Single Pass Spectral Sparsification in Dynamic Streams. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Yuan Li, Alexander A. Razborov, Benjamin Rossman |
On the AC0 Complexity of Subgraph Isomorphism. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Zengfeng Huang, Ke Yi 0001 |
The Communication Complexity of Distributed epsilon-Approximations. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Bernhard Haeupler |
Interactive Channel Capacity Revisited. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Arkadev Chattopadhyay, Jaikumar Radhakrishnan, Atri Rudra |
Topology Matters in Communication. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Nabil H. Mustafa, Rajiv Raman 0001, Saurabh Ray |
Settling the APX-Hardness Status for Geometric Set Cover. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | George Giakkoupis, Philipp Woelfel |
Randomized Mutual Exclusion with Constant Amortized RMR Complexity on the DSM. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Shaddin Dughmi |
On the Hardness of Signaling. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Radu Curticapean, Dániel Marx |
Complexity of Counting Subgraphs: Only the Boundedness of the Vertex-Cover Number Counts. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Gregory Valiant, Paul Valiant |
An Automatic Inequality Prover and Instance Optimal Identity Testing. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Tobias Christiani, Rasmus Pagh |
Generating k-Independent Variables in Constant Time. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Oded Goldreich 0001, Dana Ron |
On Learning and Testing Dynamic Environments. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Joshua A. Grochow, Toniann Pitassi |
Circuit Complexity, Proof Complexity, and Polynomial Identity Testing. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Ilan Komargodski, Tal Moran, Moni Naor, Rafael Pass, Alon Rosen, Eylon Yogev |
One-Way Functions and (Im)Perfect Obfuscation. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Craig Gentry, Shai Halevi, Mariana Raykova 0001, Daniel Wichs |
Outsourcing Private RAM Computation. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | |
55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014 |
FOCS |
2014 |
DBLP BibTeX RDF |
|
1 | Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh 0001 |
Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Leonid Gurvits, Alex Samorodnitsky |
Bounds on the Permanent and Some Applications. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Avishay Tal |
Shrinkage of De Morgan Formulae by Spectral Techniques. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Vipul Goyal, Silas Richelson, Alon Rosen, Margarita Vald |
An Algebraic Approach to Non-malleability. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Sian-Jheng Lin, Wei-Ho Chung, Yunghsiang S. Han |
Novel Polynomial Basis and Its Application to Reed-Solomon Erasure Codes. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Moshe Babaioff, Nicole Immorlica, Brendan Lucier, S. Matthew Weinberg |
A Simple and Approximately Optimal Mechanism for an Additive Buyer. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | François Le Gall |
Improved Quantum Algorithm for Triangle Finding via Combinatorial Arguments. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Mark Braverman, Klim Efremenko |
List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Amirali Abdullah, Alexandr Andoni, Ravindran Kannan, Robert Krauthgamer |
Spectral Approaches to Nearest Neighbor Search. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Bartlomiej Bosek, Dariusz Leniowski, Piotr Sankowski, Anna Zych |
Online Bipartite Matching in Offline Time. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|
1 | Barna Saha |
The Dyck Language Edit Distance Problem in Near-Linear Time. |
FOCS |
2014 |
DBLP DOI BibTeX RDF |
|