| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Sharat Ibrahimpur, Chaitanya Swamy |
Approximation Algorithms for Stochastic Minimum-Norm Combinatorial Optimization.  |
FOCS  |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Nico Döttling, Sanjam Garg, Vipul Goyal, Giulio Malavolta |
Laconic Conditional Disclosure of Secrets and Applications. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Mohsen Ghaffari 0001, Fabian Kuhn, Jara Uitto |
Conditional Hardness Results for Massively Parallel Computation from Distributed Lower Bounds. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Vincent Cohen-Addad, Michal Pilipczuk, Marcin Pilipczuk |
A Polynomial-Time Approximation Scheme for Facility Location on Planar Graphs. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Jan van den Brand, Thatchaphol Saranurak |
Sensitive Distance and Reachability Oracles for Large Batch Updates. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Soheil Behnezhad, MohammadTaghi Hajiaghayi, David G. Harris 0001 |
Exponentially Faster Massively Parallel Maximal Matching. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Dorit Aharonov, Alex Bredariol Grilo |
Stoquastic PCP vs. Randomness. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Jan van den Brand, Danupon Nanongkai, Thatchaphol Saranurak |
Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Lijie Chen 0001, Ce Jin 0001, R. Ryan Williams |
Hardness Magnification for all Sparse NP Languages. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Josh Alman, Lijie Chen 0001 |
Efficient Construction of Rigid Matrices Using an NP Oracle. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Luke Postle |
Linear-Time and Efficient Distributed Algorithms for List Coloring Graphs on Surfaces. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Anindya De, Elchanan Mossel, Joe Neeman |
Junta Correlation is Testable. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Shiri Chechik, Tianyi Zhang 0008 |
Fully Dynamic Maximal Independent Set in Expected Poly-Log Update Time. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Ankit Garg, Visu Makam, Rafael Mendes de Oliveira, Avi Wigderson |
More Barriers for Rank Methods, via a "numeric to Symbolic" Transfer. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Vasilis Kontonis, Christos Tzamos, Manolis Zampetakis |
Efficient Truncated Statistics with Unknown Truncation. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | David Zuckerman (eds.) |
60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019 |
FOCS |
2019 |
DBLP BibTeX RDF |
|
| 1 | Jacob Holm, Valerie King, Mikkel Thorup, Or Zamir, Uri Zwick |
Random k-out Subgraph Leaves only O(n/k) Inter-Component Edges. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Alex Bredariol Grilo, William Slofstra, Henry Yuen |
Perfect Zero Knowledge for Quantum Multiprover Interactive Proofs. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Zeyu Guo 0001, Mrinal Kumar 0001, Ramprasad Saptharishi, Noam Solomon |
Derandomization from Algebraic Hardness: Treading the Borders. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Aviad Rubinstein, Saeed Seddighin, Zhao Song 0002, Xiaorui Sun |
Approximation Algorithms for LCS and LIS with Truly Improved Running Times. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Aditya Bhaskara, Aidao Chen, Aidan Perreault, Aravindan Vijayaraghavan |
Smoothed Analysis in Unsupervised Learning via Decoupling. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Scott Aaronson, Daniel Grier, Luke Schaeffer |
A Quantum Query Complexity Trichotomy for Regular Languages. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrei A. Krokhin, Jakub Oprsal |
The Complexity of 3-Colouring H-Colourable Graphs. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael Chapman, Nati Linial, Yuval Peled |
Expander Graphs - Both Local and Global. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Pravesh Kothari, Sahil Singla 0001, Divyarthi Mohan, Ariel Schvartzman, S. Matthew Weinberg |
Approximation Schemes for a Unit-Demand Buyer with Independent Items via Symmetries. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Lijie Chen 0001 |
Non-deterministic Quasi-Polynomial Time is Average-Case Hard for ACC Circuits. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Cliff Stein 0001, Madhu Sudan 0001 |
Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai |
A New Deterministic Algorithm for Dynamic Set Cover. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Artur Czumaj, Christian Sohler |
A Characterization of Graph Properties Testable for General Planar Graphs with one-Sided Error (It's all About Forbidden Subgraphs). |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Dimitris Achlioptas, Fotis Iliopoulos, Alistair Sinclair |
Beyond the Lovász Local Lemma: Point to Set Correlations and Their Algorithmic Applications. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Zsolt Bartha, Nike Sun, Yumeng Zhang |
Breaking of 1RSB in Random Regular MAX-NAE-SAT. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | David G. Harris 0001 |
Distributed Local Approximation Algorithms for Maximum Matching in Graphs and Hypergraphs. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Tomer Ezra, Michal Feldman, Eric Neyman, Inbal Talgam-Cohen, S. Matthew Weinberg |
Settling the Communication Complexity of Combinatorial Auctions with Two Subadditive Buyers. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Makrand Sinha, Ronald de Wolf |
Exponential Separation between Quantum Communication and Logarithm of Approximate Rank. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Seth Neel, Aaron Roth 0001, Zhiwei Steven Wu |
How to Use Heuristics for Differential Privacy. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Peter Bürgisser, Cole Franks, Ankit Garg, Rafael Mendes de Oliveira, Michael Walter 0005, Avi Wigderson |
Towards a Theory of Non-Commutative Optimization: Geodesic 1st and 2nd Order Methods for Moment Maps and Polytopes. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Alkida Balliu, Sebastian Brandt 0002, Juho Hirvonen, Dennis Olivetti, Mikaël Rabie, Jukka Suomela |
Lower Bounds for Maximal Matchings and Maximal Independent Sets. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Noah Stephens-Davidowitz, Vinod Vaikuntanathan |
SETH-Hardness of Coding Problems. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Frank Ban, Xi Chen 0001, Adam Freilich, Rocco A. Servedio, Sandip Sinha |
Beyond Trace Reconstruction: Population Recovery from the Deletion Channel. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Oren Mangoubi, Nisheeth K. Vishnoi |
Faster Polytope Rounding, Sampling, and Volume Computation via a Sub-Linear Ball Walk. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Yossi Azar, Noam Touitou |
General Framework for Metric Optimization Problems with Delay or with Deadlines. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Moses Charikar, Paris Siminelakis |
Multi-resolution Hashing for Fast Pairwise Summations. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Kshitij Gajjar, Jaikumar Radhakrishnan |
Parametric Shortest Paths in Planar Graphs. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Anand Natarajan, John Wright 0004 |
NEEXP is Contained in MIP. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Jason Li 0006 |
Faster Minimum k-cut of a Simple Graph. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Vipul Goyal, Silas Richelson |
Non-Malleable Commitments using Goldreich-Levin List Decoding. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Vasileios Nakos, Zhao Song 0002, Zhengyu Wang |
(Nearly) Sample-Optimal Sparse Fourier Transform in Any Dimension; RIPless and Filterless. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Jingcheng Liu 0001, Alistair Sinclair, Piyush Srivastava 0001 |
A Deterministic Algorithm for Counting Colorings with 2-Delta Colors. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrii Arman, Pu Gao, Nicholas C. Wormald |
Fast Uniform Generation of Random Graphs with Given Degree Sequences. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Jaroslaw Blasiok, Patrick Lopatto, Kyle Luh, Jake Marcinek, Shravas Rao |
An Improved Lower Bound for Sparse Reconstruction from Subsampled Hadamard Matrices. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Jad Silbak, Swastik Kopparty, Ronen Shaltiel |
Quasilinear Time List-Decodable Codes for Space Bounded Channels. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Lacki, Vahab S. Mirrokni |
Near-Optimal Massively Parallel Graph Connectivity. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrea Montanari |
Optimization of the Sherrington-Kirkpatrick Hamiltonian. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Nicole Immorlica, Karthik Abinav Sankararaman, Robert E. Schapire, Aleksandrs Slivkins |
Adversarial Bandits with Knapsacks. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Nicola Galesi, Leszek Aleksander Kolodziejczyk, Neil Thapen |
Polynomial Calculus Space and Resolution Width. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Nima Anari, Alireza Rezaei 0001 |
A Tight Analysis of Bethe Approximation for Permanent. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Moses Ganardi, Artur Jez, Markus Lohrey |
Balancing Straight-Line Programs. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, Sahil Singla 0001, Sam Chiu-wai Wong |
Faster Matroid Intersection. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | David Saulpic, Vincent Cohen-Addad, Andreas Emil Feldmann |
Near-Linear Time Approximations Schemes for Clustering in Doubling Metrics. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Anurag Anshu, Naresh Goud Boddu, Dave Touchette |
Quantum Log-Approximate-Rank Conjecture is Also False. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Alexandru Gheorghiu, Thomas Vidick |
Computationally-Secure and Composable Remote State Preparation. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Alexander S. Wein, Ahmed El Alaoui, Cristopher Moore |
The Kikuchi Hierarchy and Tensor PCA. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Matthew Joseph, Jieming Mao, Seth Neel, Aaron Roth 0001 |
The Role of Interactivity in Local Differential Privacy. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Emmanuel Abbe, Min Ye 0005 |
Reed-Muller Codes Polarize. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Tsz Chiu Kwok, Lap Chi Lau, Akshay Ramachandran |
Spectral Analysis of Matrix Scaling and Operator Scaling. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Ján Pich, Rahul Santhanam |
Why are Proof Complexity Lower Bounds Hard? |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Bernhard Haeupler |
Optimal Document Exchange and New Codes for Insertions and Deletions. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Benny Applebaum, Eliran Kachlon |
Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Albert Atserias, Moritz Müller |
Automating Resolution is NP-Hard. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Mary Cryan, Heng Guo 0001, Giorgos Mousa |
Modified log-Sobolev Inequalities for Strongly Log-Concave Distributions. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Enric Boix-Adserà, Matthew S. Brennan, Guy Bresler |
The Average-Case Complexity of Counting Cliques in Erdős-Rényi Hypergraphs. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Vincent Cohen-Addad, Karthik C. S. |
Inapproximability of Clustering in Lp Metrics. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Yotam Dikstein, Irit Dinur |
Agreement Testing Theorems on Layered Set Systems. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Hung Le 0001, Shay Solomon |
Truly Optimal Euclidean Spanners. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Omri Ben-Eliezer, Clément L. Canonne, Shoham Letzter, Erik Waingarten |
Finding Monotone Patterns in Sublinear Time. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Cynthia Dwork, Michael P. Kim, Omer Reingold, Guy N. Rothblum, Gal Yona |
Learning from Outcomes: Evidence-Based Rankings. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Aditya Bhaskara, Silvio Lattanzi, Sergei Vassilvitskii, Morteza Zadimoghaddam |
Residual Based Sampling for Online Low Rank Approximation. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Sergey Bravyi 0001, David Gosset, Robert König, Marco Tomamichel |
Quantum Advantage with Noisy Shallow Circuits in 3D. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Elazar Goldenberg, Robert Krauthgamer, Barna Saha |
Sublinear Algorithms for Gap Edit Distance. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Kevin Pratt |
Waring Rank, Parameterized and Exact Algorithms. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Sepehr Assadi, Sahil Singla 0001 |
Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Ilan Reuven Cohen, Binghui Peng, David Wajc |
Tight Bounds for Online Edge Coloring. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Matthias Englert, Harald Räcke, Richard Stotz |
Polylogarithmic Guarantees for Generalized Reordering Buffer Management. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Yang P. Liu, Arun Jambulapati, Aaron Sidford |
Parallel Reachability in Almost Linear Work and Square Root Depth. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Chris Umans |
Fast Generalized DFTs for all Finite Groups. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Vida Dujmovic, Gwenaël Joret, Piotr Micek, Pat Morin, Torsten Ueckerdt, David R. Wood |
Planar Graphs have Bounded Queue-Number. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Jan van den Brand, Danupon Nanongkai |
Dynamic Approximate Shortest Paths and Beyond: Subquadratic and Worst-Case Update Time. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Ashutosh Kumar 0002, Raghu Meka, Amit Sahai |
Leakage-Resilient Secret Sharing Against Colluding Parties. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Buddhima Gamlath, Michael Kapralov, Andreas Maggiori, Ola Svensson, David Wajc |
Online Matching with General Arrivals. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Noam Lifshitz, Dor Minzer |
Noise Sensitivity on the p -Biased Hypercube. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Chao Tao 0003, Qin Zhang 0001, Yuan Zhou 0007 |
Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-armed Bandits. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Klim Efremenko, Gillat Kol, Raghuvansh Saxena |
Radio Network Coding Requires Logarithmic Overhead. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Vedat Levi Alev, Fernando Granha Jeronimo, Madhur Tulsiani |
Approximating Constraint Satisfaction Problems on High-Dimensional Expanders. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Nikhil Bansal 0001, Ola Svensson, Luca Trevisan |
New Notions and Constructions of Sparsification for Graphs and Hypergraphs. |
FOCS |
2019 |
DBLP DOI BibTeX RDF |
|
| 1 | Yossi Azar, Noam Touitou |
Improved Online Algorithm for Weighted Flow Time. |
FOCS |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Hossein Esfandiari, Michael Mitzenmacher |
Metric Sublinear Algorithms via Linear Sampling. |
FOCS |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Asaf Ferber, Vishesh Jain |
1-Factorizations of Pseudorandom Graphs. |
FOCS |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Yoichi Iwata, Yutaro Yamaguchi 0001, Yuichi Yoshida |
0/1/All CSPs, Half-Integral A-Path Packing, and Linear-Time FPT Algorithms. |
FOCS |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Akash Kumar 0003, C. Seshadhri 0001, Andrew Stolman |
Finding Forbidden Minors in Sublinear Time: A n^1/2+o(1)-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs. |
FOCS |
2018 |
DBLP DOI BibTeX RDF |
|
| 1 | Omar Fawzi, Antoine Grospellier, Anthony Leverrier |
Constant Overhead Quantum Fault-Tolerance with Quantum Expander Codes. |
FOCS |
2018 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")
data released under the ODC-BY 1.0 license