Conferences · eligible papers
FOCS
2022–2026 LIVE
2023 · 142 papers
このEditionに反映済みのmain full research papersのみ掲載しています。著者リンクは日本の大学への著者別所属根拠がある場合に限ります。
- A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow
日本大学: 関与なし（対象大学）
- A New Approach to Post-Quantum Non-Malleability
日本大学: 関与なし（対象大学）
- A Randomized Algorithm for Single-Source Shortest Path on Undirected Real-Weighted Graphs
日本大学: 関与なし（対象大学）
- A d1/2+o(1) Monotonicity Tester for Boolean Functions on d-Dimensional Hypergrids*
日本大学: 関与なし（対象大学）
- A deterministic near-linear time approximation scheme for geometric transportation
日本大学: 関与なし（対象大学）
- A proof that Reed-Muller codes achieve Shannon capacity on symmetric channels
日本大学: 関与なし（対象大学）
- A strong composition theorem for junta complexity and the boosting of property testers
日本大学: 関与なし（対象大学）
- ABE for Circuits with poly (λ) -sized Keys from LWE
日本大学: 関与なし（対象大学）
- Advisor-Verifier-Prover Games and the Hardness of Information Theoretic Cryptography
日本大学: 関与なし（対象大学）
- Agnostic proper learning of monotone functions: beyond the black-box correction barrier
日本大学: 関与なし（対象大学）
- Algorithmic Decorrelation and Planted Clique in Dependent Random Graphs: The Case of Extra Triangles
日本大学: 関与なし（対象大学）
- All-Pairs Max-Flow is no Harder than Single-Pair Max-Flow: Gomory-Hu Trees in Almost-Linear Time
日本大学: 関与なし（対象大学）
- Approximating Edit Distance in the Fully Dynamic Model
日本大学: 関与なし（対象大学）
- Attribute-Based Encryption for Circuits of Unbounded Depth from Lattices
日本大学: 関与なし（対象大学）
- Beyond Moments: Robustly Learning Affine Transformations with Asymptotically Optimal Error
日本大学: 関与なし（対象大学）
- Bounding the Quantum Value of Compiled Nonlocal Games: From CHSH to BQP Verification
日本大学: 関与なし（対象大学）
- Bridge Girth: A Unifying Notion in Network Design
日本大学: 関与なし（対象大学）
- Canonical decompositions of 3-connected graphs
日本大学: 関与なし（対象大学）
- Certified Hardness vs. Randomness for Log-Space
日本大学: 関与なし（対象大学）
- Chasing Positive Bodies
日本大学: 関与なし（対象大学）
- Clique Is Hard on Average for Unary Sherali-Adams
日本大学: 関与なし（対象大学）
- Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space
日本大学: 関与なし（対象大学）
- Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements
日本大学: 関与なし（対象大学）
- Computing linear sections of varieties: quantum entanglement, tensor decompositions and beyond
日本大学: 関与なし（対象大学）
- Constant Approximation for Private Interdependent Valuations
日本大学: 関与なし（対象大学）
- Constant-Factor Approximation Algorithms for Convex Cover and Hidden Set in a Simple Polygon
日本大学: 関与なし（対象大学）
- Convergence of Approximate and Packet Routing Equilibria to Nash Flows Over Time
日本大学: 関与なし（対象大学）
- Covering Planar Metrics (and Beyond): O(1) Trees Suffice
日本大学: 関与なし（対象大学）
- Derandomization vs Refutation: A Unified Framework for Characterizing Derandomization
日本大学: 関与なし（対象大学）
- Deterministic Clustering in High Dimensional Spaces: Sketches and Approximation
日本大学: 関与なし（対象大学）
- Deterministic Fully Dynamic SSSP and More
日本大学: 関与なし（対象大学）
- Directed Acyclic Outerplanar Graphs Have Constant Stack Number
日本大学: 関与なし（対象大学）
- Distribution of the threshold for the symmetric perceptron
日本大学: 関与なし（対象大学）
- Doubley-Efficient Interactive Proofs for Distribution Properties
日本大学: 関与なし（対象大学）
- Dynamic (1+ϵ)-Approximate Matching Size in Truly Sublinear Update Time
日本大学: 関与なし（対象大学）
- Dynamic treewidth
日本大学: 関与なし（対象大学）
- Dynamic “Succincter”
日本大学: 関与なし（対象大学）
- Efficient Algorithms for Semirandom Planted CSPs at the Refutation Threshold
日本大学: 関与なし（対象大学）
- Envy-Free Cake-Cutting for Four Agents
日本大学: 関与なし（対象大学）
- Explicit orthogonal and unitary designs
日本大学: 関与なし（対象大学）
- Exponential quantum speedup in simulating coupled classical oscillators*
日本大学: 関与なし（対象大学）
- Extracting Randomness from Samplable Distributions, Revisited
日本大学: 関与なし（対象大学）
- Fast Numerical Multivariate Multipoint Evaluation
日本大学: 関与なし（対象大学）
- Faster Algorithms for Text-to-Pattern Hamming Distances
日本大学: 関与なし（対象大学）
- Faster High Accuracy Multi-Commodity Flow from Single-Commodity Techniques
日本大学: 関与なし（対象大学）
- Faster Matrix Multiplication via Asymmetric Hashing
日本大学: 関与なし（対象大学）
- Faster high-accuracy log-concave sampling via algorithmic warm starts
日本大学: 関与なし（対象大学）
- Flip-width: Cops and Robber on dense graphs
日本大学: 関与なし（対象大学）
- Folklore Sampling is Optimal for Exact Hopsets: Confirming the √n Barrier
日本大学: 関与なし（対象大学）
- Fourier Growth of Communication Protocols for XOR Functions
日本大学: 関与なし（対象大学）
- From Grassmannian to Simplicial High-Dimensional Expanders
日本大学: 関与なし（対象大学）
- Generalizations of Matrix Multiplication can solve the Light Bulb Problem
日本大学: 関与なし（対象大学）
- Gilbert and Varshamov Meet Johnson: List-Decoding Explicit Nearly-Optimal Binary Codes
日本大学: 関与なし（対象大学）
- Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
日本大学: 関与なし（対象大学）
- HDX Condensers
日本大学: 関与なし（対象大学）
- Handling Correlated Rounding Error via Preclustering: A 1.73-approximation for Correlation Clustering
日本大学: 関与なし（対象大学）
- Hidden Permutations to the Rescue: Multi-Pass Streaming Lower Bounds for Approximate Matchings
日本大学: 関与なし（対象大学）
- IOPs with Inverse Polynomial Soundness Error
日本大学: 関与なし（対象大学）
- Improved Approximations for Vector Bin Packing via Iterative Randomized Rounding
日本大学: 関与なし（対象大学）
- Improved Hardness of Approximating k-Clique under ETH
日本大学: 関与なし（対象大学）
- Improved Streaming Algorithms for Maximum Directed Cut via Smoothed Snapshots
日本大学: 関与なし（対象大学）
- Interior-point methods on manifolds: theory and applications
日本大学: 名古屋大学
- Kolmogorov Comes to Cryptomania: On Interactive Kolmogorov Complexity and Key-Agreement
日本大学: 関与なし（対象大学）
- Krylov Methods are (nearly) Optimal for Low-Rank Approximation
日本大学: 関与なし（対象大学）
- Learning in Pessiland via Inductive Inference
日本大学: 東京科学大学
- Lipschitz Continuous Algorithms for Graph Problems
日本大学: 東京大学
- List Decoding of Tanner and Expander Amplified Codes from Distance Certificates
日本大学: 豊田工業大学
- Local Computation Algorithms for Maximum Matching: New Lower Bounds
日本大学: 関与なし（対象大学）
- Locally Uniform Hashing
日本大学: 関与なし（対象大学）
- Matrix Completion in Almost-Verification Time
日本大学: 関与なし（対象大学）
- Memory-Query Tradeoffs for Randomized Convex Optimization
日本大学: 関与なし（対象大学）
- Near Optimal Memory-Regret Tradeoff for Online Learning
日本大学: 関与なし（対象大学）
- Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster!
日本大学: 関与なし（対象大学）
- New Lower Bounds for Adaptive Tolerant Junta Testing
日本大学: 関与なし（対象大学）
- On Lifting Integrality Gaps to SSEH Hardness for Globally Constrained CSPs
日本大学: 関与なし（対象大学）
- On Pseudolinear Codes for Correcting Adversarial Errors
日本大学: 関与なし（対象大学）
- On Symmetric Factorizations of Hankel Matrices
日本大学: 関与なし（対象大学）
- On small-depth Frege proofs for PHP
日本大学: 関与なし（対象大学）
- One Tree to Rule Them All: Poly-Logarithmic Universal Steiner Tree
日本大学: 関与なし（対象大学）
- Online Ordinal Problems: Optimality of Comparison-based Algorithms and their Cardinal Complexity
日本大学: 関与なし（対象大学）
- Optimal Algorithms for Bounded Weighted Edit Distance
日本大学: 関与なし（対象大学）
- Optimal Fault-Tolerant Spanners in Euclidean and Doubling Metrics: Breaking the Ω (log n) Lightness Barrier
日本大学: 関与なし（対象大学）
- Optimal PAC Bounds without Uniform Convergence
日本大学: 関与なし（対象大学）
- Optimal Testing of Generalized Reed-Muller Codes in Fewer Queries
日本大学: 関与なし（対象大学）
- Optimal mixing of the down-up walk on independent sets of a given size
日本大学: 関与なし（対象大学）
- Parallel Repetition for the GHZ Game: Exponential Decay
日本大学: 関与なし（対象大学）
- Parameterized Approximation Schemes for Clustering with General Norm Objectives
日本大学: 関与なし（対象大学）
- Path-Reporting Distance Oracles with Logarithmic Stretch and Size O(n log log n)
日本大学: 関与なし（対象大学）
- Planar Disjoint Paths, Treewidth, and Kernels
日本大学: 関与なし（対象大学）
- Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1*
日本大学: 関与なし（対象大学）
- Polynomial-Time Pseudodeterministic Construction of Primes
日本大学: 関与なし（対象大学）
- Proof of the Clustered Hadwiger Conjecture
日本大学: 関与なし（対象大学）
- Properly learning decision trees with queries is NP-hard
日本大学: 関与なし（対象大学）
- Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming
日本大学: 関与なし（対象大学）
- Quartic Samples Suffice for Fourier Interpolation
日本大学: 関与なし（対象大学）
- Query lower bounds for log-concave sampling
日本大学: 関与なし（対象大学）
- Query-optimal estimation of unitary channels in diamond distance
日本大学: 関与なし（対象大学）
- Randomly Punctured Reed-Solomon Codes Achieve the List Decoding Capacity over Polynomial-Size Alphabets
日本大学: 関与なし（対象大学）
- ReSQueing Parallel and Private Stochastic Convex Optimization
日本大学: 関与なし（対象大学）
- SAT Reduces to the Minimum Circuit Size Problem with a Random Oracle
日本大学: 関与なし（対象大学）