Conferences · eligible papers
FOCS
2022–2026 LIVE
2024 · 133 papers
このEditionに反映済みのmain full research papersのみ掲載しています。著者リンクは日本の大学への著者別所属根拠がある場合に限ります。
- $\prod_{2}^{P}$ vs PSpace Dichotomy for the Quantified Constraint Satisfaction Problem
日本大学: 関与なし（対象大学）
- A Computational Test of Contextuality and, Even Simpler Proofs of Quantumness
日本大学: 関与なし（対象大学）
- A Dense Model Theorem for the Boolean Slice
日本大学: 関与なし（対象大学）
- A Lossless Deamortization for Dynamic Greedy Set Cover
日本大学: 関与なし（対象大学）
- A Sampling Lovász Local Lemma for Large Domain Sizes
日本大学: 関与なし（対象大学）
- A Strong Separation for Adversarially Robust ℓ0 Estimation for Linear Sketches
日本大学: 関与なし（対象大学）
- A Stronger Bound for Linear 3-LCC
日本大学: 関与なし（対象大学）
- Agnostically Learning Multi-Index Models with Queries
日本大学: 関与なし（対象大学）
- Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality
日本大学: 関与なし（対象大学）
- An Improved Line-Point Low-Degree Test*
日本大学: 関与なし（対象大学）
- An Improved Pseudopolynomial Time Algorithm for Subset Sum
日本大学: 関与なし（対象大学）
- An Optimal Algorithm for Sorting Pattern-Avoiding Sequences
日本大学: 関与なし（対象大学）
- An XOR Lemma for Deterministic Communication Complexity
日本大学: 関与なし（対象大学）
- Approximation Algorithms for Noncommutative CSPs
日本大学: 関与なし（対象大学）
- Benchmark-Tight Approximation Ratio of Simple Mechanism for a Unit-Demand Buyer
日本大学: 関与なし（対象大学）
- Boosting Uniformity in Quasirandom Groups: Fast and Simple
日本大学: 関与なし（対象大学）
- Canonical Forms for Matrix Tuples in Polynomial Time
日本大学: 関与なし（対象大学）
- Capacity Threshold for the Ising Perceptron
日本大学: 関与なし（対象大学）
- Certifying Almost All Quantum States with Few Single-Qubit Measurements
日本大学: 関与なし（対象大学）
- Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the $\sqrt{n}$ Dimension Threshold
日本大学: 関与なし（対象大学）
- Chernoff Bounds and Reverse Hypercontractivity on HDX
日本大学: 関与なし（対象大学）
- Commitments are Equivalent to Statistically-Verifiable One-Way State Generators
日本大学: 関与なし（対象大学）
- Communication Separations for Truthful Auctions: Breaking the Two-Player Barrier
日本大学: 関与なし（対象大学）
- Computational Dynamical Systems
日本大学: 関与なし（対象大学）
- Computational Hardness of Detecting Graph Lifts and Certifying Lift-Monotone Properties of Random Regular Graphs
日本大学: 関与なし（対象大学）
- Computing Approximate Centerpoints in Polynomial Time
日本大学: 関与なし（対象大学）
- Computing the 3-Edge-Connected Components of Directed Graphs in Linear Time
日本大学: 関与なし（対象大学）
- Constant Degree Direct Product Testers with Small Soundness
日本大学: 関与なし（対象大学）
- Constant-Depth Arithmetic Circuits for Linear Algebra Problems
日本大学: 関与なし（対象大学）
- Cycles of Well-Linked Sets and an Elementary Bound for the Directed Grid Theorem
日本大学: 関与なし（対象大学）
- Decoding Quasi-Cyclic Quantum LDPC Codes
日本大学: 関与なし（対象大学）
- Deterministic Algorithm and Faster Algorithm for Submodular Maximization Subject to a Matroid Constraint
日本大学: 関与なし（対象大学）
- Directed Isoperimetry and Monotonicity Testing: A Dynamical Approach
日本大学: 関与なし（対象大学）
- Distinguishing, Predicting, and Certifying: On the Long Reach of Partial Notions of Pseudorandomness
日本大学: 関与なし（対象大学）
- Dot-Product Proofs and Their Applications
日本大学: 関与なし（対象大学）
- Dynamic Deterministic Constant-Approximate Distance Oracles with $n^{\epsilon}$ Worst-Case Update Time
日本大学: 関与なし（対象大学）
- Efficient Approximate Unitary Designs from Random Pauli Rotations
日本大学: 関与なし（対象大学）
- Efficient Approximation of Fractional Hypertree Width
日本大学: 関与なし（対象大学）
- Efficient Certificates of Anti-Concentration Beyond Gaussians
日本大学: 関与なし（対象大学）
- Efficient Statistics With Unknown Truncation, Polynomial Time Algorithms, Beyond Gaussians
日本大学: 関与なし（対象大学）
- Efficient Unitary Designs from Random Sums and Permutations
日本大学: 関与なし（対象大学）
- Efficient and Near-Optimal Noise Generation for Streaming Differential Privacy
日本大学: 関与なし（対象大学）
- Expansion of High-Dimensional Cubical Complexes: with Application to Quantum Locally Testable Codes
日本大学: 関与なし（対象大学）
- Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning
日本大学: 関与なし（対象大学）
- Exponential Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs
日本大学: 関与なし（対象大学）
- Fast Decision Tree Learning Solves Hard Coding-Theoretic Problems
日本大学: 関与なし（対象大学）
- Fast List Decoding of Univariate Multiplicity and Folded Reed-Solomon Codes
日本大学: 関与なし（対象大学）
- Fast Mixing in Sparse Random Ising Models*
日本大学: 関与なし（対象大学）
- Faster $(\Delta+1)$-Edge Coloring: Breaking the $m\sqrt{n}$ Time Barrier
日本大学: 関与なし（対象大学）
- Faster Isomorphism Testing of $p$-Groups of Frattini Class 2
日本大学: 関与なし（対象大学）
- First-Order Model Checking on Monadically Stable Graph Classes
日本大学: 関与なし（対象大学）
- Fully Dynamic $k-\text{Clustering}$ with Fast Update Time and Small Recourse
日本大学: 関与なし（対象大学）
- Fully Dynamic Matching and Ordered Ruzsa-Szemerédi Graphs
日本大学: 関与なし（対象大学）
- Gapped Clique Homology on Weighted Graphs is QMA1-Hard and Contained in QMA
日本大学: 関与なし（対象大学）
- Gaussian Approximation of Convex Sets by Intersections of Halfspaces*
日本大学: 関与なし（対象大学）
- Gradient Descent for Unbounded Convex Functions on Hadamard Manifolds and its Applications to Scaling Problems
- Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems
日本大学: 関与なし（対象大学）
- Hardness of Approximate Sperner and Applications to Envy-Free Cake Cutting
日本大学: 関与なし（対象大学）
- Hardness of Packing, Covering and Partitioning Simple Polygons with Unit Squares
日本大学: 関与なし（対象大学）
- High-Temperature Gibbs States are Unentangled and Efficiently Preparable
日本大学: 関与なし（対象大学）
- How to Simulate Random Oracles with Auxiliary Input
日本大学: 関与なし（対象大学）
- Improved Condensers for Chor-Goldreich Sources
日本大学: 関与なし（対象大学）
- Improved Distance (Sensitivity) Oracles with Subquadratic Space
日本大学: 関与なし（対象大学）
- Instance-Optimality in I/O-Efficient Sampling and Sequential Estimation
日本大学: 関与なし（対象大学）
- Interactive Proofs for General Distribution Properties
日本大学: 関与なし（対象大学）
- Jump Operators, Interactive Proofs and Proof Complexity Generators
日本大学: 関与なし（対象大学）
- Lempel-Ziv (LZ77) Factorization in Sublinear Time
日本大学: 関与なし（対象大学）
- Locally Stationary Distributions: A Framework for Analyzing Slow-Mixing Markov Chains*
日本大学: 関与なし（対象大学）
- Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs
日本大学: 関与なし（対象大学）
- Maximum Flow by Augmenting Paths in $n^{2+o(1)}$ Time
日本大学: 関与なし（対象大学）
- Minor Containment and Disjoint Paths in Almost-Linear Time
日本大学: 関与なし（対象大学）
- Naively Sorting Evolving Data is Optimal and Robust
日本大学: 関与なし（対象大学）
- Near-Optimal $\left(1+\epsilon\right)-\text{Approximate}$ Fully-Dynamic All-Pairs Shortest Paths in Planar Graphs
日本大学: 関与なし（対象大学）
- Near-Optimal Deterministic Network Decomposition and Ruling Set, and Improved MIS
日本大学: 関与なし（対象大学）
- Near-Optimal Size Linear Sketches for Hypergraph Cut Sparsifiers
日本大学: 関与なし（対象大学）
- Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles
日本大学: 関与なし（対象大学）
- Nearly Optimal List Labeling
日本大学: 関与なし（対象大学）
- New Structures and Algorithms for Length-Constrained Expander Decompositions
日本大学: 関与なし（対象大学）
- Novel Properties of Hierarchical Probabilistic Partitions and Their Algorithmic Applications
日本大学: 関与なし（対象大学）
- O(1) Insertion for Random Walk d-ary Cuckoo Hashing up to the Load Threshold
日本大学: 関与なし（対象大学）
- Obstructions to Erdös-Pósa Dualities for Minors
日本大学: 関与なし（対象大学）
- On Approximate Fully-Dynamic Matching and Online Matrix-Vector Multiplication
日本大学: 関与なし（対象大学）
- On Approximating Cutwidth and Pathwidth
日本大学: 関与なし（対象大学）
- On Pigeonhole Principles and Ramsey in TFNP
日本大学: 関与なし（対象大学）
- On Robustness to $k$-Wise Independence of Optimal Bayesian Mechanisms
日本大学: 関与なし（対象大学）
- On the Complexity of Avoiding Heavy Elements
日本大学: 関与なし（対象大学）
- On the Existence of Seedless Condensers: Exploring the Terrain
日本大学: 関与なし（対象大学）
- Online Combinatorial Allocations and Auctions with Few Samples
日本大学: 関与なし（対象大学）
- Optimal Bounds for Open Addressing Without Reordering
日本大学: 関与なし（対象大学）
- Optimal Coding for Randomized Kolmogorov Complexity and Its Applications
日本大学: 東京科学大学
- Optimal Quantile Estimation: Beyond the Comparison Model
日本大学: 関与なし（対象大学）
- Optimal Tradeoffs for Estimating Pauli Observables
日本大学: 関与なし（対象大学）
- Polynomial Calculus Sizes Over the Boolean and Fourier Bases are Incomparable
日本大学: 関与なし（対象大学）
- Power Series Composition in Near-Linear Time
日本大学: 東京科学大学
- Predict to Minimize Swap Regret for All Payoff-Bounded Tasks
日本大学: 関与なし（対象大学）
- Proofs of Space with Maximal Hardness
日本大学: 関与なし（対象大学）
- Quantum Computational Advantage with Constant-Temperature Gibbs Sampling
日本大学: 関与なし（対象大学）
- Quantum Eigenvalue Processing
日本大学: 関与なし（対象大学）
- Ramsey Theorems for Trees and a General ‘Private Learning Implies Online Learning’ Theorem
日本大学: 関与なし（対象大学）
- Random Gabidulin Codes Achieve List Decoding Capacity in the Rank Metric
日本大学: 関与なし（対象大学）