- Lunjia Hu, Yifan Wu:
Predict to Minimize Swap Regret for All Payoff-Bounded Tasks. FOCS 2024: 244-263 - Brice Huang:
Capacity Threshold for the Ising Perceptron. FOCS 2024: 1126-1136 - Hsin-Yuan Huang, John Preskill, Mehdi Soleimanifar:
Certifying Almost All Quantum States with Few Single-Qubit Measurements. FOCS 2024: 1202-1206 - Yuta Inoue, Ken-ichi Kawarabayashi, Atsuyuki Miyashita, Bojan Mohar, Tomohiro Sonobe:
Three-Edge-Coloring Projective Planar Cubic Graphs: A Generalization of the Four Color Theorem. FOCS 2024: 86-105 - Gábor Ivanyos, Euan J. Mendoza, Youming Qiao, Xiaorui Sun, Chuanqi Zhang:
Faster Isomorphism Testing of p-Groups of Frattini Class 2. FOCS 2024: 1408-1424 - Siddharth Iyer, Anup Rao:
An XOR Lemma for Deterministic Communication Complexity. FOCS 2024: 429-432 - Matthew Jenssen, Will Perkins, Aditya Potukuchi, Michael Simkin:
Sampling, Counting, and Large Deviations for Triangle-Free Graphs Near the Critical Density. FOCS 2024: 151-165 - Yaonan Jin, Pinyan Lu:
Benchmark-Tight Approximation Ratio of Simple Mechanism for a Unit-Demand Buyer. FOCS 2024: 1251-1259 - Gil Kalai, Noam Lifshitz, Dor Minzer, Tamar Ziegler:
A Dense Model Theorem for the Boolean Slice. FOCS 2024: 797-805 - Dominik Kempa, Tomasz Kociumaka:
Lempel-Ziv (LZ77) Factorization in Sublinear Time. FOCS 2024: 2045-2055 - Erfan Khaniki:
Jump Operators, Interactive Proofs and Proof Complexity Generators. FOCS 2024: 573-593 - Sanjeev Khanna, Aaron Putterman, Madhu Sudan:
Near-Optimal Size Linear Sketches for Hypergraph Cut Sparsifiers. FOCS 2024: 1669-1706 - Robbie King, Tamara Kohler:
Gapped Clique Homology on Weighted Graphs is QMA1-Hard and Contained in QMA. FOCS 2024: 493-504 - Yasunori Kinoshita, Baitian Li:
Power Series Composition in Near-Linear Time. FOCS 2024: 2180-2185 - Viktoriia Korchemna, Daniel Lokshtanov, Saket Saurabh, Vaishali Surianarayanan, Jie Xue:
Efficient Approximation of Fractional Hypertree Width. FOCS 2024: 754-779 - Tuukka Korhonen, Michal Pilipczuk, Giannos Stamoulis:
Minor Containment and Disjoint Paths in Almost-Linear Time. FOCS 2024: 53-61 - Oliver Korten, Toniann Pitassi:
Strong vs. Weak Range Avoidance and the Linear Ordering Principle. FOCS 2024: 1388-1407 - Pravesh K. Kothari, Peter Manohar:
Exponential Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs. FOCS 2024: 1802-1845 - Dmitriy Kunisky, Cristopher Moore, Alexander S. Wein:
Tensor Cumulants for Statistical Inference on Invariant Distributions. FOCS 2024: 1007-1026 - Dmitriy Kunisky, Xifan Yu:
Computational Hardness of Detecting Graph Lifts and Certifying Lift-Monotone Properties of Random Regular Graphs. FOCS 2024: 1621-1633 - Jane H. Lee, Anay Mehrotra, Manolis Zampetakis:
Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians. FOCS 2024: 988-1006 - Jiatu Li, Edward Pyne, Roei Tell:
Distinguishing, Predicting, and Certifying: On the Long Reach of Partial Notions of Pseudorandomness. FOCS 2024: 1-13 - Yang P. Liu:
On Approximate Fully-Dynamic Matching and Online Matrix-Vector Multiplication. FOCS 2024: 228-243 - Kuikui Liu, Sidhanth Mohanty, Prasad Raghavendra, Amit Rajaraman, David X. Wu:
Locally Stationary Distributions: A Framework for Analyzing Slow-Mixing Markov Chains. FOCS 2024: 203-215 - Kuikui Liu, Sidhanth Mohanty, Amit Rajaraman, David X. Wu:
Fast Mixing in Sparse Random Ising Models. FOCS 2024: 120-128 - Guang Hao Low, Yuan Su:
Quantum Eigenvalue Processing. FOCS 2024: 1051-1062 - Zhenjian Lu, Igor C. Oliveira, Hanlin Ren, Rahul Santhanam:
On the Complexity of Avoiding Heavy Elements. FOCS 2024: 2403-2412 - Tony Metger, Anand Natarajan, Tina Zhang:
Succinct Arguments for QMA from Standard Assumptions via Compiled Nonlocal Games. FOCS 2024: 1193-1201 - Tony Metger, Alexander Poremba, Makrand Sinha, Henry Yuen:
Simple Constructions of Linear-Depth t-Designs and Pseudorandom Unitaries. FOCS 2024: 485-492 - Sasank Mouli:
Polynomial Calculus Sizes Over the Boolean and Fourier Bases are Incomparable. FOCS 2024: 790-796
