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