| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Ashwin Sah, Mehtaab Sawhney |
Distribution of the threshold for the symmetric perceptron.  |
FOCS  |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Ishaq Aden-Ali, Yeshwanth Cherapanamjeri, Abhishek Shetty, Nikita Zhivotovskiy |
Optimal PAC Bounds without Uniform Convergence. |
FOCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Venkatesan Guruswami, Jun-Ting Hsieh, Pravesh K. Kothari, Peter Manohar |
Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold. |
FOCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Ofer Grossman, Meghal Gupta, Mark Sellke |
Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting. |
FOCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Yang Cai 0001, Ziyun Chen, Jinzhao Wu |
Simultaneous Auctions are Approximately Revenue-Optimal for Subadditive Bidders. |
FOCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Shunhua Jiang, Binghui Peng, Omri Weinstein |
The Complexity of Dynamic Least-Squares Regression. |
FOCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Or Meir |
Toward Better Depth Lower Bounds: A KRW-like theorem for Strong Composition. |
FOCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Dominik Kempa, Tomasz Kociumaka |
Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space. |
FOCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Hsien-Chih Chang, Jonathan Conroy, Hung Le 0001, Lazar Milenkovic, Shay Solomon, Cuong Than |
Covering Planar Metrics (and Beyond): O(1) Trees Suffice. |
FOCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Mehrdad Ghadiri |
On Symmetric Factorizations of Hankel Matrices. |
FOCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Badih Ghazi, Rahul Ilango, Pritish Kamath, Ravi Kumar 0001, Pasin Manurangsi |
Towards Separating Computational and Statistical Differential Privacy. |
FOCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Xin Lyu 0002, Avishay Tal, Hongxun Wu, Junzhao Yang |
Tight Time-Space Lower Bounds for Constant-Pass Learning. |
FOCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Ran Duan, Hongxun Wu, Renfei Zhou |
Faster Matrix Multiplication via Asymmetric Hashing. |
FOCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Shuichi Hirahara, Mikito Nanashima |
Learning in Pessiland via Inductive Inference. |
FOCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Nathan Klein, Neil Olver |
Thin Trees for Laminar Families. |
FOCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Kasper Green Larsen, Huacheng Yu |
Super-Logarithmic Lower Bounds for Dynamic Graph Problems. |
FOCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Suprovat Ghoshal, Euiwoong Lee |
On Lifting Integrality Gaps to SSEH Hardness for Globally Constrained CSPs. |
FOCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Ariel Kulik, Matthias Mnich, Hadas Shachnai |
Improved Approximations for Vector Bin Packing via Iterative Randomized Rounding. |
FOCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Jane Lange, Arsen Vasilyan |
Agnostic proper learning of monotone functions: beyond the black-box correction barrier. |
FOCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Ruzomberka, Homa Nikbakht, Christopher G. Brinton, H. Vincent Poor |
On Pseudolinear Codes for Correcting Adversarial Errors. |
FOCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Greg Bodwin, Gary Hoppenworth, Ohad Trabelsi |
Bridge Girth: A Unifying Notion in Network Design. |
FOCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Ryan Babbush, Dominic W. Berry, Robin Kothari, Rolando D. Somma, Nathan Wiebe |
Exponential quantum speedup in simulating coupled classical oscillators*. |
FOCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Xi Chen, Shyamal Patel |
New Lower Bounds for Adaptive Tolerant Junta Testing. |
FOCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Vincent Cohen-Addad, David Saulpic, Chris Schwiegelshohn |
Deterministic Clustering in High Dimensional Spaces: Sketches and Approximation. |
FOCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Xi Chen, Binghui Peng |
Memory-Query Tradeoffs for Randomized Convex Optimization. |
FOCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Marshall Ball, Eli Goldin, Dana Dachman-Soled, Saachi Mutreja |
Extracting Randomness from Samplable Distributions, Revisited. |
FOCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Jonathan A. Kelner, Jerry Li 0001, Allen Liu, Aaron Sidford, Kevin Tian |
Matrix Completion in Almost-Verification Time. |
FOCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Paul Jungeblut, Laura Merker, Torsten Ueckerdt |
Directed Acyclic Outerplanar Graphs Have Constant Stack Number. |
FOCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Mehrdad Ghadiri, Richard Peng, Santosh S. Vempala |
The Bit Complexity of Efficient Continuous Optimization. |
FOCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Vincent Cohen-Addad, Euiwoong Lee, Shi Li 0001, Alantha Newman |
Handling Correlated Rounding Error via Preclustering: A 1.73-approximation for Correlation Clustering. |
FOCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Itay Cohen 0003, Roy Roth, Amnon Ta-Shma |
HDX Condensers. |
FOCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Zhao Song 0002, Baocheng Sun 0002, Omri Weinstein, Ruizhe Zhang 0001 |
Quartic Samples Suffice for Fourier Interpolation. |
FOCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Adam Karczmarz, Piotr Sankowski |
Sensitivity and Dynamic Distance Oracles via Generic Matrices and Frobenius Form. |
FOCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Anand Natarajan, Tina Zhang |
Bounding the Quantum Value of Compiled Nonlocal Games: From CHSH to BQP Verification. |
FOCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Jeongwan Haah, Robin Kothari, Ryan O'Donnell, Ewin Tang |
Query-optimal estimation of unitary channels in diamond distance. |
FOCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Ryan O'Donnell, Rocco A. Servedio, Pedro Paredes 0002 |
Explicit orthogonal and unitary designs. |
FOCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Zander Kelley, Raghu Meka |
Strong Bounds for 3-Progressions. |
FOCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Josh Alman, Hengjie Zhang |
Generalizations of Matrix Multiplication can solve the Light Bulb Problem. |
FOCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Sitan Chen, Brice Huang, Jerry Li 0001, Allen Liu, Mark Sellke |
When Does Adaptivity Help for Quantum State Learning? |
FOCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Yair Carmon, Arun Jambulapati, Yujia Jin, Yin Tat Lee, Daogao Liu, Aaron Sidford, Kevin Tian |
ReSQueing Parallel and Private Stochastic Convex Optimization. |
FOCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | He Jia, Pravesh K. Kothari, Santosh S. Vempala |
Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error. |
FOCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Costas Busch, Da Qi Chen, Arnold Filtser, Daniel Hathcock, D. Ellis Hershkowitz, Rajmohan Rajaraman |
One Tree to Rule Them All: Poly-Logarithmic Universal Steiner Tree. |
FOCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Ainesh Bakshi, Shyam Narayanan |
Krylov Methods are (nearly) Optimal for Low-Rank Approximation. |
FOCS |
2023 |
DBLP DOI BibTeX RDF |
|
| 1 | Sébastien Bubeck, Christian Coester, Yuval Rabani |
Shortest Paths without a Map, but with an Entropic Regularizer. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Tsz Chiu Kwok, Lap Chi Lau, Kam Chuen Tung |
Cheeger Inequalities for Vertex Expansion and Reweighted Eigenvalues. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Takashi Yamakawa, Mark Zhandry |
Verifiable Quantum Advantage without Structure. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Manik Dhar, Zeev Dvir |
Linear Hashing with ℓ∞ guarantees and two-sided Kakeya bounds. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Mina Dalirrooyfard, Virginia Vassilevska Williams |
Induced Cycles and Paths Are Harder Than You Think. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Baihe Huang, Shunhua Jiang, Zhao Song 0002, Runzhou Tao, Ruizhe Zhang 0001 |
Solving SDP Faster: A Robust IPM Framework and Efficient Implementation. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Adam Brown, Aditi Laddha, Madhusudhan Pittu, Mohit Singh, Prasad Tetali |
Determinant Maximization via Matroid Intersection Algorithms. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Tali Kaufman, Dor Minzer |
Improved Optimal Testing Results from Global Hypercontractivity. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Shuichi Hirahara |
NP-Hardness of Learning Programs and Partial MCSP. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Shimon Kogan, Merav Parter |
Having Hope in Hops: New Spanners, Preservers and Lower Bounds for Hopsets. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Gil Cohen, Tal Yankovitz |
Relaxed Locally Decodable and Correctable Codes: Beyond Tensoring. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Ashish Chiplunkar, John Kallaugher, Michael Kapralov, Eric Price 0001 |
Factorial Lower Bounds for (Almost) Random Order Streams. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Fernando Granha Jeronimo, Tushant Mittal, Sourya Roy, Avi Wigderson |
Almost Ramanujan Expanders from Arbitrary Expanders via Operator Amplification. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Panagiotis Charalampopoulos, Tomasz Kociumaka, Philip Wellnitz |
Faster Pattern Matching under Edit Distance : A Reduction to Dynamic Puzzle Matching and the Seaweed Monoid of Permutation Matrices. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Joao Basso, David Gamarnik, Song Mei, Leo Zhou |
Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Vishwas Bhargava, Sumanta Ghosh, Zeyu Guo 0001, Mrinal Kumar 0001, Chris Umans |
Fast Multivariate Multipoint Evaluation Over All Finite Fields. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Dimitrios M. Thilikos, Sebastian Wiederrecht |
Killing a vortex. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Harm Derksen, Emanuele Viola |
Fooling polynomials using invariant theory*. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Charlie Carlson, Ewan Davies, Nicolas Fraiman, Alexandra Kolla, Aditya Potukuchi, Corrine Yap |
Algorithms for the ferromagnetic Potts model on expanders. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Artur Czumaj, Shaofeng H.-C. Jiang, Robert Krauthgamer, Pavel Veselý 0001, Mingwei Yang 0002 |
Streaming Facility Location in High Dimension via Geometric Hashing. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Mitali Bafna, Jun-Ting Hsieh, Pravesh K. Kothari, Jeff Xu |
Polynomial-Time Power-Sum Decomposition of Polynomials. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Deeparnab Chakrabarty, Andrei Graur, Haotian Jiang, Aaron Sidford |
Improved Lower Bounds for Submodular Function Minimization. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Alexandr Andoni, Negev Shekel Nosatzki, Sandip Sinha, Clifford Stein 0001 |
Estimating the Longest Increasing Subsequence in Nearly Optimal Time. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Jane Lange, Ronitt Rubinfeld, Arsen Vasilyan |
Properly learning monotone functions via local correction. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Sepehr Assadi, Gillat Kol, Zhijun Zhang 0007 |
Rounds vs Communication Tradeoffs for Maximal Independent Sets. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Yu Chen 0039, Sanjeev Khanna, Huan Li 0002 |
On Weighted Graph Sparsification by Linear Sketching. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael Kapralov, Mikhail Makarov, Sandeep Silwal, Christian Sohler, Jakab Tardos |
Motif Cut Sparsifiers. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Jeongwan Haah, Robin Kothari, Ewin Tang |
Optimal learning of quantum Hamiltonians from high-temperature Gibbs states. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Omer Paneth, Rafael Pass |
Incrementally Verifiable Computation via Rate-1 Batch Arguments. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Li Chen 0028, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva |
Maximum Flow and Minimum-Cost Flow in Almost-Linear Time. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Kun He 0011, Chunyang Wang, Yitong Yin |
Sampling Lovász local lemma for general constraint satisfaction solutions in near-linear time. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Virginia Vassilevska Williams, Eyob Woldeghebriel, Yinzhan Xu |
Algorithms and Lower Bounds for Replacement Paths under Multiple Edge Failure. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Elazar Goldenberg, Tomasz Kociumaka, Robert Krauthgamer, Barna Saha |
Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | David Gamarnik, Eren C. Kizildag, Will Perkins 0001, Changji Xu |
Algorithms and Barriers in the Symmetric Binary Perceptron Model. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Hanlin Ren, Rahul Santhanam, Zhikun Wang |
On the Range Avoidance Problem for Circuits. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Cameron Musco, Christopher Musco, David P. Woodruff, Taisuke Yasuda 0002 |
Active Linear Regression for ℓp Norms and Beyond. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Rasmus Kyng, Simon Meierhans, Maximilian Probst |
Derandomizing Directed Random Walks in Almost-Linear Time. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Vincent Cohen-Addad, Euiwoong Lee, Alantha Newman |
Correlation Clustering with Sherali-Adams. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Hamed Hatami, Pooya Hatami |
The Implicit Graph Conjecture is False. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Alexander Meiburg |
Inapproximability of Positive Semidefinite Permanents and Quantum State Tomography. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Lijie Chen 0001, Ron D. Rothblum, Roei Tell |
Unstructured Hardness to Average-Case Randomness. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Pranjal Dutta, Nitin Saxena 0001 |
Separated borders: Exponential-gap fanin-hierarchy theorem for approximative depth-3 circuits. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Tony Metger, Omar Fawzi, David Sutter, Renato Renner |
Generalised entropy accumulation. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Jinyoung Park, Huy Tuan Pham |
A Proof of the Kahn-Kalai Conjecture. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Ahmed El Alaoui, Andrea Montanari, Mark Sellke |
Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael A. Bender, Alex Conway, Martin Farach-Colton, Hanna Komlós, William Kuszmaul, Nicole Wein |
Online List Labeling: Breaking the log2n Barrier. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Xi Chen 0001, Christos H. Papadimitriou, Binghui Peng |
Memory Bounds for Continual Learning. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Aaron Bernstein, Danupon Nanongkai, Christian Wulff-Nilsen |
Negative-Weight Single-Source Shortest Paths in Near-linear Time. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Arnold Filtser, Hung Le 0001 |
Low Treewidth Embeddings of Planar and Minor-Free Metrics. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | David P. Woodruff, Taisuke Yasuda 0002 |
High-Dimensional Geometric Streaming in Polynomial Space. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Nashlen Govindasamy, Tuomas Hakoniemi, Iddo Tzameret |
Simple Hard Instances for Low-Depth Algebraic Proofs. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Nima Anari, Yang P. Liu, Thuy-Duong Vuong |
Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Marvin Künnemann |
A tight (non-combinatorial) conditional lower bound for Klee's Measure Problem in 3D. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Christian Ikenmeyer, Igor Pak |
What is in #P and what is not? |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Lalita Devadas, Rishab Goyal, Yael Kalai, Vinod Vaikuntanathan |
Rate-1 Non-Interactive Arguments for Batch-NP and Applications. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Jan van den Brand, Sebastian Forster, Yasamin Nazari |
Fast Deterministic Fully Dynamic Distance Approximation. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
| 1 | Jiayu Zhang |
Classical Verification of Quantum Computations in Linear Time. |
FOCS |
2022 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")
data released under the ODC-BY 1.0 license