Conferences · eligible papers
FOCS
2021–2025 確定版
2025 · 136 papers
このEditionに反映済みのmain full research papersのみ掲載しています。著者リンクは日本の大学への著者別所属根拠がある場合に限ります。
- Query-Efficient Fixpoints of ℓp-Contractions
日本大学: 関与なし（対象大学）
- RE-completeness of entangled constraint satisfaction problems
日本大学: 関与なし（対象大学）
- Radial Isotropic Position via an Implicit Newton’s Method
日本大学: 関与なし（対象大学）
- Ramanujan bigraphs and applications
日本大学: 関与なし（対象大学）
- Random Reed-Solomon Codes and Random Linear Codes are Locally Equivalent
日本大学: 関与なし（対象大学）
- Random-Shift Revisited: Tight Approximations for Tree Embeddings and ℓ₁-Oblivious Routings
日本大学: 関与なし（対象大学）
- Rank Bounds and PIT for depth-4 circuits with top fan-in 3 and constant bottom fan-in via a non-linear Edelstein-Kelly theorem
日本大学: 関与なし（対象大学）
- Rapid Mixing on Random Regular Graphs beyond Uniqueness
日本大学: 関与なし（対象大学）
- Robust Learning of Multi-index Models via Iterative Subspace Approximation
日本大学: 関与なし（対象大学）
- Robust Local Testability of Tensor Products of Constant-Rate Algebraic Geometry Codes
日本大学: 関与なし（対象大学）
- Root Ridge Leverage Score Sampling for ℓp Subspace Approximation
日本大学: 関与なし（対象大学）
- Round Elimination via Self-Reduction: Closing Gaps for Distributed Maximal Matching
日本大学: 関与なし（対象大学）
- Shortest Paths on Convex Polyhedral Surfaces
日本大学: 関与なし（対象大学）
- Shuffling Cards When You Are of Very Little Brain: Low Memory Generation of Permutations
日本大学: 関与なし（対象大学）
- Sign-Rank of k-Hamming Distance is Constant
日本大学: 関与なし（対象大学）
- Solving Linear Inequalities over the Space of Convex Sets & its Applications to Cryptography and Hydrodynamics
日本大学: 関与なし（対象大学）
- Solving Zero-Sum Games with Fewer Matrix-Vector Products
日本大学: 関与なし（対象大学）
- Static Retrieval Revisited: To Optimality and Beyond
日本大学: 関与なし（対象大学）
- Stochastic Knapsack without Relaxing the Capacity
日本大学: 関与なし（対象大学）
- Stochastic scheduling with Bernoulli-type jobs through policy stratification
日本大学: 関与なし（対象大学）
- Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa
日本大学: 関与なし（対象大学）
- Stronger Cell Probe Lower Bounds via Local PRGs
日本大学: 関与なし（対象大学）
- Succinct Homomorphic MACs from Groups and Applications
日本大学: 関与なし（対象大学）
- The Power of Recursive Embeddings for ℓp Metrics
日本大学: 関与なし（対象大学）
- The Proof Analysis Problem
日本大学: 関与なし（対象大学）
- The Quasi-Polynomial Low-Degree Conjecture is False
日本大学: 関与なし（対象大学）
- The Sponge Is Quantum Indifferentiable
日本大学: 関与なし（対象大学）
- Theoretical limitations of multi-layer Transformer
日本大学: 関与なし（対象大学）
- Tight Low Degree Hardness for Optimizing Pure Spherical Spin Glasses
日本大学: 関与なし（対象大学）
- Tight Pair Query Lower Bounds for Matching and Earth Mover’s Distance
日本大学: 関与なし（対象大学）
- Towards True Work-Efficiency in Parallel Derandomization: MIS, Maximal Matching, and Hitting Set
日本大学: 関与なし（対象大学）
- Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimension
日本大学: 関与なし（対象大学）
- Truthful and Almost Envy-Free Mechanism of Allocating Indivisible Goods: the Power of Randomness
日本大学: 関与なし（対象大学）
- Undirected Multicast Network Coding Gaps via Locally Decodable Codes
日本大学: 関与なし（対象大学）
- Weighted k-Path and Other Problems in Almost O*(2k) Deterministic Time via Dynamic Representative Sets†
日本大学: 関与なし（対象大学）
- ℓ2/ℓ2 Sparse Recovery via Weighted Hypergraph Peeling
日本大学: 関与なし（対象大学）