Conferences · eligible papers
FOCS
2022–2026 LIVE
2025 · 136 papers
このEditionに反映済みのmain full research papersのみ掲載しています。著者リンクは日本の大学への著者別所属根拠がある場合に限ります。
- A Dense Neighborhood Lemma: Applications of Partial Concept Classes to Domination and Chromatic Number
日本大学: 関与なし（対象大学）
- A Distillation-Teleportation Protocol for Fault-Tolerant QRAM
日本大学: 関与なし（対象大学）
- A Little Clairvoyance Is All You Need
日本大学: 関与なし（対象大学）
- A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams
日本大学: 関与なし（対象大学）
- A kq/q-2 Lower Bound for Odd Query Locally Decodable Codes from Bipartite Kikuchi Graphs
日本大学: 関与なし（対象大学）
- Adaptivity Gaps for Stochastic Probing with Subadditive Functions
日本大学: 関与なし（対象大学）
- Adversarially Robust Quantum State Learning and Testing
日本大学: 関与なし（対象大学）
- Almost Tight Additive Guarantees for k-Edge-Connectivity
日本大学: 関与なし（対象大学）
- An Improved Bound for the Beck-Fiala Conjecture
日本大学: 関与なし（対象大学）
- An Improved Greedy Approximation for (Metric) k-Means
日本大学: 関与なし（対象大学）
- Approximating High-Dimensional Earth Mover’s Distance as Fast as Closest Pair
日本大学: 関与なし（対象大学）
- Asymptotically Optimal Inapproximability of Ek-SAT Reconfiguration
日本大学: 関与なし（対象大学）
- Average Distortion Sketching
日本大学: 関与なし（対象大学）
- Beyond Regularity: Simple versus Optimal Mechanisms, Revisited
日本大学: 関与なし（対象大学）
- Binary Codes for Computationally Bounded Errors Under Standard Crypto Assumptions
日本大学: 関与なし（対象大学）
- Bipartite Matching is in Catalytic Logspace
日本大学: 関与なし（対象大学）
- Breaking a Long-Standing Barrier: 2-ε Approximation for Steiner Forest
日本大学: 関与なし（対象大学）
- Characterization of Priority-Neutral Matching Lattices
日本大学: 関与なし（対象大学）
- Collapsing Catalytic Classes
日本大学: 関与なし（対象大学）
- Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs
日本大学: 関与なし（対象大学）
- Complexity theory of orbit closure intersection for tensors: reductions, completeness, and graph isomorphism hardness
日本大学: 関与なし（対象大学）
- Computational-Statistical Tradeoffs from NP-hardness
日本大学: 関与なし（対象大学）
- Computing the Polytope Diameter is Even Harder than NP-hard (Already for Perfect Matchings)
日本大学: 関与なし（対象大学）
- Constant Approximation of Arboricity in Near-Optimal Sublinear Time
日本大学: 関与なし（対象大学）
- Constant Rate Codes for Adaptive Broadcasts Do Not Exist
日本大学: 関与なし（対象大学）
- Cryptography Meets Worst-case Complexity: Optimal Security and More From iO and Worst-case Assumptions
日本大学: 関与なし（対象大学）
- Cycle-factors of regular graphs via entropy
日本大学: 関与なし（対象大学）
- Density Measures for Language Generation
日本大学: 関与なし（対象大学）
- Deterministic Almost-Linear-Time Gomory-Hu Trees
日本大学: 関与なし（対象大学）
- Deterministic Counting from Coupling Independence
日本大学: 関与なし（対象大学）
- Deterministic factorization of constant-depth algebraic circuits in subexponential time
日本大学: 関与なし（対象大学）
- Direct Product Theorems for Randomized Query Complexity
日本大学: 関与なし（対象大学）
- Distance Approximating Minors for Planar and Minor-Free Graphs
日本大学: 関与なし（対象大学）
- Distributed Triangle Detection is Hard in Few Rounds
日本大学: 関与なし（対象大学）
- Dynamic Dyck and Tree Edit Distance: Decompositions and Reductions to String Edit Distance*
日本大学: 関与なし（対象大学）
- Dynamic Treewidth in Logarithmic Time
日本大学: 関与なし（対象大学）
- Edge-weighted Matching in the Dark
日本大学: 関与なし（対象大学）
- Efficiently Batching Unambiguous Interactive Proofs
日本大学: 関与なし（対象大学）
- Embeddings into Similarity Measures for Nearest Neighbor Search
日本大学: 関与なし（対象大学）
- Explicit Lossless Vertex Expanders
日本大学: 関与なし（対象大学）
- Exponential improvements to the average-case hardness of BosonSampling
日本大学: 関与なし（対象大学）
- Extractors for Samplable Distributions with Polynomially Small Min-Entropy
日本大学: 関与なし（対象大学）
- Factorization norms and an inverse theorem for MaxCut
日本大学: 関与なし（対象大学）
- Fast Algorithms for Graph Arboricity and Related Problems
日本大学: 関与なし（対象大学）
- Faster Exact Learning of k-Term DNFs with Membership and Equivalence Queries
日本大学: 関与なし（対象大学）
- Faster Logconcave Sampling from a Cold Start in High Dimension
日本大学: 関与なし（対象大学）
- Faster Mixing of the Jerrum-Sinclair Chain
日本大学: 関与なし（対象大学）
- Finding Colorings in One-Sided Expanders
日本大学: 関与なし（対象大学）
- Fingerprint Filters Are Optimal
日本大学: 関与なし（対象大学）
- Gap-preserving reductions and RE-completeness of independent set games
日本大学: 関与なし（対象大学）
- Generalized Flow in Nearly-linear Time on Moderately Dense Graphs
日本大学: 関与なし（対象大学）
- Group Order is in QCMA
日本大学: 名古屋大学
- Gödel in Cryptography: Effectively Zero-Knowledge Proofs for NP with No Interaction, No Setup, and Perfect Soundness
日本大学: 関与なし（対象大学）
- Handling LP-Rounding for Hierarchical Clustering and Fitting Distances by Ultrametrics
日本大学: 関与なし（対象大学）
- High-to-Low Dimensional PPA-completeness: Borsuk-Ulam, Tucker, Consensus Halving, and Ham Sandwich
日本大学: 関与なし（対象大学）
- How Global Calibration Strengthens Multiaccuracy
日本大学: 関与なし（対象大学）
- Implicit High-Order Moment Tensor Estimation and Learning Latent Variable Models
日本大学: 関与なし（対象大学）
- Improved 2-Approximate Shortest Paths for close vertex pairs
日本大学: 関与なし（対象大学）
- Improved Lower Bounds for all Odd-Query Locally Decodable Codes
日本大学: 関与なし（対象大学）
- Improved Round-by-round Soundness IOPs via Reed-Muller Codes
日本大学: 関与なし（対象大学）
- Inapproximability of Finding Sparse Vectors in Codes, Subspaces, and Lattices
日本大学: 関与なし（対象大学）
- Incompressibility and Spectral Gaps of Random Circuits
日本大学: 関与なし（対象大学）
- Ineffectiveness for Search and Undecidability of PCSP Meta-Problems
日本大学: 関与なし（対象大学）
- Instance-Optimal Uniformity Testing and Tracking
日本大学: 関与なし（対象大学）
- Integer multiplication is at least as hard as matrix transposition*
日本大学: 関与なし（対象大学）
- Integral Online Algorithms for Set Cover and Load Balancing with Convex Objectives
日本大学: 関与なし（対象大学）
- Kronecker Powers, Orthogonal Vectors, and the Asymptotic Spectrum
日本大学: 関与なし（対象大学）
- Learning quantum Gibbs states locally and efficiently
日本大学: 関与なし（対象大学）
- List Decoding Expander-Based Codes up to Capacity in Near-Linear Time*
日本大学: 豊田工業大学
- Lower Bounds for Non-adaptive Local Computation Algorithms
日本大学: 関与なし（対象大学）
- Maximally Extendable Product Codes are Good Coboundary Expanders
日本大学: 関与なし（対象大学）
- More efficient sifting for grid norms, and applications to multiparty communication complexity
日本大学: 関与なし（対象大学）
- Multi-Pass Streaming Lower Bounds for Approximating Max-Cut
日本大学: 関与なし（対象大学）
- NP-hardness of the Minimum Circuit Size Problem from Well-Studied Assumptions
日本大学: 関与なし（対象大学）
- Near-Asymptotically-Good Quantum Codes with Transversal CCZ Gates and Sublinear-Weight Parity-Checks
日本大学: 関与なし（対象大学）
- Near-Optimal Algorithms for Omniprediction
日本大学: 関与なし（対象大学）
- Near-Optimal Fault-Tolerant Strong Connectivity Preservers
日本大学: 関与なし（対象大学）
- Near-Optimal Property Testers for Pattern Matching
日本大学: 関与なし（対象大学）
- Nearly Tight Regret Bounds for Profit Maximization in Bilateral Trade
日本大学: 関与なし（対象大学）
- Obfuscation of Unitary Quantum Programs
日本大学: 関与なし（対象大学）
- On Inverse Theorems and Combinatorial Lines
日本大学: 関与なし（対象大学）
- On Succinct Obfuscation via Propositional Proofs
日本大学: 関与なし（対象大学）
- On optimal distinguishers for Planted Clique
日本大学: 関与なし（対象大学）
- On the Impossibility of SNARGs with Short CRS : (or: Revisiting Gentry-Wichs Barrier in the Non-adaptive Setting)
日本大学: 関与なし（対象大学）
- On the Parallel Complexity of Finding a Matroid Basis
日本大学: 関与なし（対象大学）
- Online Edge Coloring: Sharp Thresholds
日本大学: 関与なし（対象大学）
- Optimal 4-Approximation for the Correlated Pandora’s Problem
日本大学: 関与なし（対象大学）
- Optimal Smoothed Analysis of the Simplex Method
日本大学: 関与なし（対象大学）
- Optimal Trickle-Down Theorems for Path Complexes via C-Lorentzian Polynomials with Applications to Sampling and Log-Concave Sequences
日本大学: 関与なし（対象大学）
- Overcomplete Tensor Decomposition via Koszul-Young Flattenings
日本大学: 関与なし（対象大学）
- PTF Testing Lower Bounds for Non-Gaussian Component Analysis
日本大学: 関与なし（対象大学）
- Parallel (1+ε)-Approximate Multi-Commodity Min-Cost Flow in Almost Optimal Depth and Work
日本大学: 関与なし（対象大学）
- Parallel Repetition for Post-Quantum Arguments
日本大学: 関与なし（対象大学）
- Paths and Intersections: Exact Emulators for Planar Graphs
日本大学: 関与なし（対象大学）
- Pattern Matching under Weighted Edit Distance
日本大学: 総合研究大学院大学
- Perfect Lp Sampling with Polylogarithmic Update Time
日本大学: 関与なし（対象大学）
- Polynomial bounds for the Graph Minor Structure Theorem
日本大学: 関与なし（対象大学）
- Polynomial-Time Approximation Schemes via Utility Alignment: Unit-Demand Pricing and More
日本大学: 関与なし（対象大学）
- Proving Natural Distribution Properties is Harder than Testing Them
日本大学: 関与なし（対象大学）
- Quasipolynomial Bounds for the Corners Theorem
日本大学: 関与なし（対象大学）