FOCSTheoretical Computer Science
IEEE Annual Symposium on Foundations of Computer Science
765Papers indexed
2020-2025Years covered
Recent papers
- A Dense Neighborhood Lemma: Applications of Partial Concept Classes to Domination and Chromatic NumberRomain Bourneuf, Pierre Charbit, Stéphan Thomassé2025 · 13 citations
- A Distillation-Teleportation Protocol for Fault-Tolerant QRAMAlexander M. Dalzell, András Gilyén, Connor T. Hann, Sam McArdle et al.2025 · 12 citations
- A kq/q-2 Lower Bound for Odd Query Locally Decodable Codes from Bipartite Kikuchi GraphsOliver Janzer, Peter Manohar2025 · 1 citation
- A Little Clairvoyance Is All You NeedAnupam Gupta, Haim Kaplan, Alexander Lindermayr, Jens Schlöter et al.2025 · 5 citations
- A Polynomial Space Lower Bound for Diameter Estimation in Dynamic StreamsSanjeev Khanna, Ashwin Padaki, Krish Singal, Erik Waingarten2025 · 3 citations
- Adaptivity Gaps for Stochastic Probing with Subadditive FunctionsJian Li, Yinchen Liu, Yiran Zhang2025 · 2 citations
- Adversarially Robust Quantum State Learning and TestingMaryam Aliakbarpour, Vladimir Braverman, Nai-Hui Chia, Yuhan Liu2025
- Almost Tight Additive Guarantees for k-Edge-ConnectivityNikhil Kumar, Chaitanya Swamy2025 · 4 citations
- An Improved Bound for the Beck-Fiala ConjectureNikhil Bansal, Haotian Jiang2025 · 2 citations
- An Improved Greedy Approximation for (Metric) k-MeansMoses Charikar, Vincent Cohen-Addad, Ruiquan Gao, Fabrizio Grandoni et al.2025 · 2 citations
- Approximating High-Dimensional Earth Mover's Distance as Fast as Closest PairLorenzo Beretta, Vincent Cohen-Addad, Rajesh Jayaram, Erik Waingarten2025 · 2 citations
- Asymptotically Optimal Inapproximability of Ek-SAT ReconfigurationShuichi Hirahara, Naoto Ohsaka2025 · 3 citations
- Average Distortion SketchingYiqiao Bao, Anubhav Baweja, Nicolas Menand, Erik Waingarten et al.2025 · 3 citations
- Beyond Regularity: Simple versus Optimal Mechanisms, RevisitedYiding Feng, Yaonan Jin2025 · 6 citations
- Binary Codes for Computationally Bounded Errors Under Standard Crypto AssumptionsGeorge Lu, Jad Silbak, Daniel Wichs2025 · 1 citation
- Bipartite Matching is in Catalytic LogspaceAryan Agarwala, Ian Mertz2025 · 15 citations
- Breaking a Long-Standing Barrier: 2-ε Approximation for Steiner ForestAli Ahmadi, Iman Gholami, MohammadTaghi Hajiaghayi, Peyman Jabbarzade et al.2025 · 2 citations
- Characterization of Priority-Neutral Matching LatticesClayton Thomas2025
- Collapsing Catalytic ClassesMichal Koucký, Ian Mertz, Edward Pyne, Sasha Sami2025 · 15 citations
- Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut GraphsAaron Bernstein, Joakim Blikstad, Jason Li, Thatchaphol Saranurak et al.2025 · 2 citations
- Complexity theory of orbit closure intersection for tensors: reductions, completeness, and graph isomorphism hardnessVladimir Lysikov, Michael Walter2025 · 3 citations
- Computational-Statistical Tradeoffs from NP-hardnessGuy Blanc, Caleb Koch, Carmen Strassle, Li-Yang Tan2025 · 2 citations
- Computing the Polytope Diameter is Even Harder than NP-hard (Already for Perfect Matchings)Lasse Wulf2025 · 2 citations
- Constant Approximation of Arboricity in Near-Optimal Sublinear TimeJiangqi Dai, Mohsen Ghaffari, Julian Portmann2025 · 1 citation
