| Breaking Barriers for Distributed MIS by Faster Degree Reduction |
Seri Khoury and Aaron Schild |
Aaron Schild |
STOC 2026 |
1 |
| How Global Calibration Strengthens Multiaccuracy |
Sílvia Casacuberta, Parikshit Gopalan, Varun Kanade, Omer Reingold |
Sílvia Casacuberta |
FOCS 2025 |
2 |
| Zero-free Regions and Concentration Inequalities for Hypergraph Colorings in the Local Lemma Regime |
Jingcheng Liu, Yixiao Yu |
Yixiao Yu |
STOC 2026 |
3 |
| Learning Read-Once Determinants and the Principal Minor Assignment Problem |
Abhiram Aravind, Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj, Chandan Saha |
Abhiram Aravind |
STOC 2026 |
4 |
| Failure of Symmetry of Information for Randomized Computations |
Jinqiao Hu, Yahel Manor, Igor Oliveira |
Jinqiao Hu |
STOC 2026 |
5 |
| Learning CNF formulas from uniform random solutions in the local lemma regime |
Weiming Feng, Xiongxin Yang, Yixiao Yu, Yiyao Zhang |
Xiongxin Yang |
STOC 2026 |
6 |
| Improved Approximation Algorithms for Multiway Cut by Large Mixtures of New and Old Rounding Schemes |
Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick |
Neng Huang |
STOC 2026 |
7 |
| Learning Mixture Models via Efficient High-dimensional Sparse Fourier Transforms |
Alkis Kalavasis, Pravesh K. Kothari, Shuchen Li, Manolis Zampetakis |
Shuchen Li |
STOC 2026 |
8 |
| Range avoidance, Arthur-Merlin, and TFNP |
Surendra Ghentiyala, Zeyong Li, Noah Stephens-Davidowitz |
Zeyong Li |
STOC 2026 |
9 |
| Deterministic list decoding of Reed-Solomon codes |
Soham Chatterjee, Mrinal Kumar, Prahladh Harsha |
Soham Chatterjee |
STOC 2026 |
10 |
| Half-Approximating Maximum Dicut in the Streaming Setting |
Amir Azarmehr, Soheil Behnezhad, Shane Ferrante, Mohammad Saneian |
Shane Ferrante |
STOC 2026 |
11 |
| Boolean function monotonicity testing requires (almost) n^1/2 queries |
Mark Chen, Xi Chen, Hao Cui, William Pires, Jonah Stockwell |
Jonah Stockwell |
STOC 2026 |
12 |
| Finding Bugs in Short Proofs: The Metamathematics of Resolution Lower Bounds |
Jiawei Li, Yuhao Li, Hanlin Ren |
Hanlin Ren |
STOC 2026 |
13 |
| Classifying Identities: Subcubic Distributivity Checking and Hardness from Arithmetic Progression Detection |
Bartłomiej Dudek, Nick Fischer, Geri Gokaj, Ce Jin, Marvin Künnemann, Xiao Mao, Mirza Redzic |
Mirza Redzic |
STOC 2026 |
14 |
| Provable Long-Range Benefits of Next-Token Prediction |
Xinyuan Cao, Santosh S. Vempala |
Xinyuan Cao |
STOC 2026 |
15 |
| SNARGs for NP from Unprovability of Mathematical Theorems (Or: How to use the simplicity of cryptographic reasoning) |
Yao-Ching Hsieh, Abhishek Jain, Jiatu Li, Surya Mathialagan |
Jiatu Li |
STOC 2026 |
16 |
| A Theory for Probabilistic Polynomial-Time Reasoning |
Lijie Chen, Jiatu Li, Igor C. Oliveira, Ryan Williams |
Jiatu Li |
STOC 2026 |
17 |
| Nash Social Welfare with Submodular Valuations: Approximation Algorithms and Integrality Gaps |
Xiaohui Bei, Yuda Feng, Yang Hu, Shi Li, Ruilong Zhang |
Ruilong Zhang |
STOC 2026 |
18 |
| Additive One Approximation for Minimum Degree Spanning Tree: Breaking the O(mn) Time Barrier |
Sayan Bhattacharya, Ermiya Farokhnejad, Haoze Wang |
Ermiya Farokhnejad |
STOC 2026 |
19 |
| On the Computational Hardness of Transformers |
Barna Saha, Yinzhan Xu, Christopher Ye, Hantao Yu |
Christopher Ye |
STOC 2026 |
20 |
| Lower Bounds for Near-Quadratic-Depth Resolution over Parities |
Sreejata Kishor Bhattacharya, Farzan Byramji, Arkadev Chattopadhyay, Russell Impagliazzo |
Farzan Byramji |
STOC 2026 |
21 |