| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Chi-Ning Chou, Alexander Golovnev, Madhu Sudan 0001, Santhoshini Velusamy |
Approximability of all finite CSPs with linear sketches.  |
FOCS  |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Ruoxu Cen, Jason Li 0006, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, Kent Quanrud |
Minimum Cuts in Directed Graphs via Partial Sparsification. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Deeparnab Chakrabarty, Yu Chen 0039, Sanjeev Khanna |
A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Heiko Dietrich, James B. Wilson |
Group isomorphism is nearly-linear time for most orders. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | William Kuszmaul, Shyam Narayanan |
Stochastic and Worst-Case Generalized Sorting Revisited. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Arnaud Casteigts, Michael Raskin, Malte Renken, Viktor Zamaraev |
Sharp Thresholds in Random Simple Temporal Graphs. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Asaf Ferber, Matthew Kwan, Lisa Sauermann |
List-decodability with large radius for Reed-Solomon codes. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Guillaume Moroz |
New data structure for univariate polynomial approximation and applications to root isolation, numerical multipoint evaluation, and other problems. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Eshan Chattopadhyay, Jesse Goodman, Jyun-Jie Liao |
Affine Extractors for Almost Logarithmic Entropy. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Robert Robere, Jeroen Zuiddam |
Amortized Circuit Complexity, Formal Complexity Measures, and Catalytic Algorithms. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Toniann Pitassi, Prasanna Ramakrishnan, Li-Yang Tan |
Tradeoffs for small-depth Frege proofs. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | David Doty, Mahsa Eftekhari, Leszek Gasieniec, Eric E. Severson, Przemyslaw Uznanski, Grzegorz Stachowiak |
A time and space optimal stable population protocol solving exact majority. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Joseph S. B. Mitchell |
Approximating Maximum Independent Set for Rectangles in the Plane. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | George Christodoulou 0001, Elias Koutsoupias, Annamária Kovács |
On the Nisan-Ronen conjecture. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Jingqiu Ding, Tommaso d'Orsi, Rajai Nasser, David Steurer |
Robust recovery for stochastic block models. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Rahul Ilango |
The Minimum Formula Size Problem is (ETH) Hard. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Anupam Gupta 0001, Gregory Kehne, Roie Levin |
Random Order Online Set Cover is as Easy as Offline. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark Braverman, Sumegha Garg, Or Zamir |
Tight Space Complexity of the Coin Problem. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright 0004, Henry Yuen |
Quantum soundness of testing tensor codes. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Tillmann Miltzow, Reinier F. Schmiermann |
On Classifying Continuous Constraint Satisfaction problems. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Nolan J. Coble, Matthew Coudron |
Quasi-polynomial Time Approximation of Output Probabilities of Geometrically-local, Shallow Quantum Circuits. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Marco Carmosino, Valentine Kabanets, Antonina Kolokolova, Igor C. Oliveira |
LEARN-Uniform Circuit Lower Bounds and Provability in Bounded Arithmetic. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Xiaoyu Chen, Weiming Feng 0001, Yitong Yin, Xinyuan Zhang |
Rapid mixing of Glauber dynamics via spectral independence for all degrees. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Akash Kumar 0003, C. Seshadhri 0001, Andrew Stolman |
Random walks and forbidden minors III: $\text{poly}\left(d\varepsilon ^{-1}\right)$-time partition oracles for minor-free graph classes. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Shyan Akmal, Ryan Williams 0001 |
MAJORITY-3SAT (and Related Problems) in Polynomial Time. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Yasuhiro Kondo, Ryuhei Mori, Ramis Movassagh |
Quantum supremacy and hardness of estimating output probabilities of quantum circuits. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Adam Bouland, Bill Fefferman, Zeph Landau, Yunchao Liu |
Noise and the Frontier of Quantum Supremacy. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Aaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol Saranurak |
Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Alessandro Chiesa, Fermi Ma, Nicholas Spooner, Mark Zhandry |
Post-Quantum Succinct Arguments: Breaking the Quantum Rewinding Barrier. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael Kapralov, Robert Krauthgamer, Jakab Tardos, Yuichi Yoshida |
Spectral Hypergraph Sparsifiers of Nearly Linear Size. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Oded Goldreich 0001, Avi Wigderson |
Non-adaptive vs Adaptive Queries in the Dense Graph Testing Model. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Yu Gao 0001, Yang P. Liu, Richard Peng |
Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg-Rao. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Guy Blanc, Jane Lange, Mingda Qiao, Li-Yang Tan |
Properly learning decision trees in almost polynomial time. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Mikkel Abrahamsen |
Covering Polygons is Even Harder. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Nika Haghtalab, Tim Roughgarden, Abhishek Shetty |
Smoothed Analysis with Adaptive Adversaries. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Oliver Korten |
The Hardest Explicit Construction. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Ruiquan Gao, Zhongtian He, Zhiyi Huang 0002, Zipei Nie, Bijun Yuan, Yan Zhong 0002 |
Improved Online Correlated Selection. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Enric Boix-Adserà, Guy Bresler, Frederic Koehler |
Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Dong Yeap Kang, Tom Kelly 0001, Daniela Kühn, Abhishek Methuku, Deryk Osthus |
A proof of the Erdös-Faber-Lovász conjecture: Algorithmic aspects. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Hans L. Bodlaender, Carla Groenland, Jesper Nederlof, Céline M. F. Swennenhuis |
Parameterized Problems Complete for Nondeterministic FPT time and Logarithmic Space. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Eshan Chattopadhyay, Jesse Goodman |
Improved Extractors for Small-Space Sources. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Vitaly Feldman, Audra McMillan, Kunal Talwar |
Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Noga Alon, Steve Hanneke, Ron Holzman, Shay Moran |
A Theory of PAC Learnability of Partial Concept Classes. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Kyriakos Axiotis, Aleksander Madry, Adrian Vladu |
Faster Sparse Minimum Cost Flow by Electrical Flow Localization. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Guy Blanc, Moses Charikar |
Multiway Online Correlated Selection. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Wenzheng Li, Jan Vondrák |
A constant-factor approximation algorithm for Nash Social Welfare with submodular valuations. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Victor Lecomte, Li-Yang Tan |
Sharper bounds on the Fourier concentration of DNFs. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Nai-Hui Chia, Kai-Min Chung, Qipeng Liu 0001, Takashi Yamakawa |
On the Impossibility of Post-Quantum Black-Box Zero-Knowledge in Constant Round. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Vincent Cohen-Addad, Debarati Das 0001, Evangelos Kipouridis, Nikos Parotsidis, Mikkel Thorup |
Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Mina Dalirrooyfard, Ray Li, Virginia Vassilevska Williams |
Hardness of Approximate Diameter: Now for Undirected Graphs. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Mohsen Ghaffari 0001, Fabian Kuhn |
Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Danny Nam, Allan Sly, Youngtak Sohn |
One-step replica symmetry breaking of random regular NAE-SAT. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Jason Li 0006, Debmalya Panigrahi, Thatchaphol Saranurak |
A Nearly Optimal All-Pairs Min-Cuts Algorithm in Simple Graphs. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Hung Le 0001, Christian Wulff-Nilsen |
Optimal Approximate Distance Oracle for Planar Graphs. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Venkatesan Guruswami, Xiaoyu He, Ray Li |
The zero-rate threshold for adversarial bit-deletions is less than 1/2. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Zeyu Guo 0001, Ray Li, Chong Shangguan, Itzhak Tamo, Mary Wootters |
Improved List-Decodability and List-Recoverability of Reed-Solomon Codes via Tree Packings: [Extended Abstract]. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Ken-ichi Kawarabayashi, Anastasios Sidiropoulos |
Embeddings of Planar Quasimetrics into Directed ℓ1 and Polylogarithmic Approximation for Directed Sparsest-Cut. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Vishesh Jain, Huy Tuan Pham, Thuy-Duong Vuong |
Towards the sampling Lovász Local Lemma. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Wenyu Jin 0001, Xiaorui Sun |
Fully Dynamic s-t Edge Connectivity in Subpolynomial Time (Extended Abstract). |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael A. Bender, Bradley C. Kuszmaul, William Kuszmaul |
Linear Probing Revisited: Tombstones Mark the Demise of Primary Clustering. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Xiao Mao |
Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Itai Dinur, Nathan Keller, Ohad Klein |
Fine-Grained Cryptanalysis: Tight Conditional Bounds for Dense k-SUM and k-XOR. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Rahul Jain 0001, Srijita Kundu |
A direct product theorem for quantum communication complexity with applications to device-independent QKD. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Anupam Gupta 0001, Amit Kumar 0001, Debmalya Panigrahi |
A Hitting Set Relaxation for $k$-Server and an Extension to Time-Windows. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Tuukka Korhonen |
A Single-Exponential Time 2-Approximation Algorithm for Treewidth. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Dorna Abdolazimi, Kuikui Liu, Shayan Oveis Gharan |
A Matrix Trickle-Down Theorem on Simplicial Complexes and Applications to Sampling Colorings. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Vera Traub, Rico Zenklusen |
A Better-Than-2 Approximation for Weighted Tree Augmentation. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Olivier Bousquet, Mark Braverman, Gillat Kol, Klim Efremenko, Shay Moran |
Statistically Near-Optimal Hypothesis Selection. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Zongchen Chen, Kuikui Liu, Eric Vigoda |
Spectral Independence via Stability and Applications to Holant-Type Problems. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Sebastian Forster, Gramoz Goranci, Yang P. Liu, Richard Peng, Xiaorui Sun, Mingquan Ye |
Minor Sparsifiers and the Distributed Laplacian Paradigm. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Zeyuan Allen-Zhu, Yuanzhi Li |
Feature Purification: How Adversarial Training Performs Robust Deep Learning. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark Braverman, Subhash Khot, Noam Lifshitz, Dor Minzer |
An Invariance Principle for the Multi-slice, with Applications. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Kaspars Balodis, Shalev Ben-David, Mika Göös, Siddhartha Jain 0002, Robin Kothari |
Unambiguous DNFs and Alon-Saks-Seymour. |
FOCS |
2021 |
DBLP DOI BibTeX RDF |
|
| 1 | Ainesh Bakshi, Nadiia Chepurko, David P. Woodruff |
Robust and Sample Optimal Algorithms for PSD Low Rank Approximation. |
FOCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal |
Rigid Matrices From Rectangular PCPs or: Hard Claims Have Complex Proofs. |
FOCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Sébastien Bubeck, Sitan Chen, Jerry Li 0001 |
Entanglement is Necessary for Optimal Quantum Property Testing. |
FOCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Max Hopkins, Daniel Kane 0001, Shachar Lovett, Gaurav Mahajan |
Point Location and Active Learning: Learning Halfspaces Almost Optimally. |
FOCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Peyman Afshani, Pingan Cheng |
2D Generalization of Fractional Cascading on Axis-aligned Planar Subdivisions. |
FOCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Ankit Garg, Neeraj Kayal, Chandan Saha 0001 |
Learning sums of powers of low-degree polynomials in the non-degenerate case. |
FOCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Noah Shutty, Mary Wootters, Patrick Hayden |
Tight Limits on Nonlocality from Nontrivial Communication Complexity; a.k.a. Reliable Computation with Asymmetric Gate Noise. |
FOCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Nima Anari, Kuikui Liu, Shayan Oveis Gharan |
Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model. |
FOCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Jonathan Mosheiff, Nicolas Resch, Noga Ron-Zewi, Shashwat Silas, Mary Wootters |
LDPC Codes Achieve List Decoding Capacity. |
FOCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Iftach Haitner, Yonatan Karidi-Heller |
A Tight Lower Bound on Adaptively Secure Full-Information Coin Flip. |
FOCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Avishay Tal |
Towards Optimal Separations between Quantum and Randomized Query Complexities. |
FOCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Ashutosh Kumar 0002, Xin Li 0006, Raghu Meka, David Zuckerman |
Extractors and Secret Sharing Against Bounded Collusion Protocols. |
FOCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Susanna F. de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere, Marc Vinyals |
Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity. |
FOCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Ariel Kulik, Hadas Shachnai |
Analysis of Two-variable Recurrence Relations with Application to Parameterized Approximations. |
FOCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Shuai Shao 0001, Jin-Yi Cai |
A Dichotomy for Real Boolean Holant Problems. |
FOCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Anupam Gupta 0001, Roie Levin |
Fully-Dynamic Submodular Cover with Bounded Recourse. |
FOCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Julia Chuzhoy, Yu Gao 0001, Jason Li 0006, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak |
A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond. |
FOCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Tommaso d'Orsi, Pravesh K. Kothari, Gleb Novikov, David Steurer |
Sparse PCA: Algorithms, Adversarial Perturbations and Certificates. |
FOCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Zvika Brakerski, Yael Tauman Kalai, Raghuvansh R. Saxena |
Deterministic and Efficient Interactive Coding from Hard-to-Decode Tree Codes. |
FOCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Anurag Anshu, Srinivasan Arunachalam, Tomotaka Kuwahara, Mehdi Soleimanifar |
Sample-efficient learning of quantum many-body systems. |
FOCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Chi-Ning Chou, Alexander Golovnev, Santhoshini Velusamy |
Optimal Streaming Approximations for all Boolean Max-2CSPs and Max-ksat. |
FOCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Amir Abboud, Robert Krauthgamer, Ohad Trabelsi |
Cut-Equivalent Trees are Optimal for Min-Cut Queries. |
FOCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Shant Boodaghians, Joshua Brakensiek, Samuel B. Hopkins, Aviad Rubinstein |
Smoothed Complexity of 2-player Nash Equilibria. |
FOCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Simon Apers, Ronald de Wolf |
Quantum Speedup for Graph Sparsification, Cut Approximation and Laplacian Solving. |
FOCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Virginia Vassilevska Williams, Yinzhan Xu |
Monochromatic Triangles, Triangle Listing and APSP. |
FOCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Zongchen Chen, Kuikui Liu, Eric Vigoda |
Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction. |
FOCS |
2020 |
DBLP DOI BibTeX RDF |
|
| 1 | Daniel Dadush, Bento Natura, László A. Végh |
Revisiting Tardos's Framework for Linear Programming: Faster Exact Solutions using Approximate Solvers. |
FOCS |
2020 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")
data released under the ODC-BY 1.0 license