Conferences · eligible papers
FOCS
2021–2025 確定版
2021 · 117 papers
このEditionに反映済みのmain full research papersのみ掲載しています。著者リンクは日本の大学への著者別所属根拠がある場合に限ります。
- 2-norm Flow Diffusion in Near-Linear Time
日本大学: 関与なし（対象大学）
- A Better-Than-2 Approximation for Weighted Tree Augmentation
日本大学: 関与なし（対象大学）
- A Gap-ETH-Tight Approximation Scheme for Euclidean TSP
日本大学: 関与なし（対象大学）
- A Hitting Set Relaxation for $k$-Server and an Extension to Time-Windows
日本大学: 関与なし（対象大学）
- A Matrix Trickle-Down Theorem on Simplicial Complexes and Applications to Sampling Colorings
日本大学: 関与なし（対象大学）
- A Nearly Optimal All-Pairs Min-Cuts Algorithm in Simple Graphs
日本大学: 関与なし（対象大学）
- A Polynomial Lower Bound on the Number of Rounds for Parallel Submodular Function Minimization
日本大学: 関与なし（対象大学）
- A Quantum Advantage for a Natural Streaming Problem
日本大学: 関与なし（対象大学）
- A Single-Exponential Time 2-Approximation Algorithm for Treewidth
日本大学: 関与なし（対象大学）
- A Theory of PAC Learnability of Partial Concept Classes
日本大学: 関与なし（対象大学）
- A constant-factor approximation algorithm for Nash Social Welfare with submodular valuations
日本大学: 関与なし（対象大学）
- A direct product theorem for quantum communication complexity with applications to device-independent QKD
日本大学: 関与なし（対象大学）
- A proof of the Erdös-Faber-Lovász conjecture: Algorithmic aspects
日本大学: 関与なし（対象大学）
- A time and space optimal stable population protocol solving exact majority
日本大学: 関与なし（対象大学）
- APMF < APSP? Gomory-Hu Tree for Unweighted Graphs in Almost-Quadratic Time
日本大学: 関与なし（対象大学）
- Affine Extractors for Almost Logarithmic Entropy
日本大学: 関与なし（対象大学）
- Almost Optimal Inapproximability of Multidimensional Packing Problems
日本大学: 関与なし（対象大学）
- Amortized Circuit Complexity, Formal Complexity Measures, and Catalytic Algorithms
日本大学: 関与なし（対象大学）
- An Invariance Principle for the Multi-slice, with Applications
日本大学: 関与なし（対象大学）
- Applications of Random Algebraic Constructions to Hardness of Approximation
日本大学: 関与なし（対象大学）
- Approximability of all finite CSPs with linear sketches
日本大学: 関与なし（対象大学）
- Approximating Maximum Independent Set for Rectangles in the Plane
日本大学: 関与なし（対象大学）
- At most 3.55n stable matchings
日本大学: 関与なし（対象大学）
- Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance
日本大学: 関与なし（対象大学）
- Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models
日本大学: 関与なし（対象大学）
- Combinatorial Contracts
日本大学: 関与なし（対象大学）
- Constructive Separations and Their Consequences
日本大学: 関与なし（対象大学）
- Continuity, Uniqueness and Long-Term Behavior of Nash Flows Over Time
日本大学: 関与なし（対象大学）
- Covering Polygons is Even Harder
日本大学: 関与なし（対象大学）
- Demystifying the border of depth-3 algebraic circuits
日本大学: 関与なし（対象大学）
- Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time
日本大学: 関与なし（対象大学）
- Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition
日本大学: 関与なし（対象大学）
- Embeddings of Planar Quasimetrics into Directed ℓ1 and Polylogarithmic Approximation for Directed Sparsest-Cut
日本大学: 関与なし（対象大学）
- Exact and Approximate Pattern Counting in Degenerate Graphs: New Algorithms, Hardness Results, and Complexity Dichotomies
日本大学: 関与なし（対象大学）
- Exponential Lower Bounds for Locally Decodable and Correctable Codes for Insertions and Deletions
日本大学: 関与なし（対象大学）
- Exponential Separations Between Learning With and Without Quantum Memory
日本大学: 関与なし（対象大学）
- FIXP-membership via Convex Optimization: Games, Cakes, and Markets
日本大学: 関与なし（対象大学）
- Faster Sparse Minimum Cost Flow by Electrical Flow Localization
日本大学: 関与なし（対象大学）
- Feature Purification: How Adversarial Training Performs Robust Deep Learning
日本大学: 関与なし（対象大学）
- Fine-Grained Cryptanalysis: Tight Conditional Bounds for Dense k-SUM and k-XOR
日本大学: 関与なし（対象大学）
- Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor
日本大学: 関与なし（対象大学）
- Fooling Constant-Depth Threshold Circuits (Extended Abstract)
日本大学: 関与なし（対象大学）
- Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg-Rao
日本大学: 関与なし（対象大学）
- Fully Dynamic s-t Edge Connectivity in Subpolynomial Time (Extended Abstract)
日本大学: 関与なし（対象大学）
- Group isomorphism is nearly-linear time for most orders
日本大学: 関与なし（対象大学）
- Hardness of Approximate Diameter: Now for Undirected Graphs
日本大学: 関与なし（対象大学）
- Hardness vs Randomness, Revised: Uniform, Non-Black-Box, and Instance-Wise
日本大学: 関与なし（対象大学）
- Harmonic Persistent Homology (extended abstract)
日本大学: 関与なし（対象大学）
- Hiding Among the Clones: A Simple and Nearly Optimal Analysis of Privacy Amplification by Shuffling
日本大学: 関与なし（対象大学）
- Hop-Constrained Metric Embeddings and their Applications
日本大学: 関与なし（対象大学）
- Improved Extractors for Small-Space Sources
日本大学: 関与なし（対象大学）
- Improved List-Decodability and List-Recoverability of Reed-Solomon Codes via Tree Packings: [Extended Abstract]
日本大学: 関与なし（対象大学）
- Improved Online Correlated Selection
日本大学: 関与なし（対象大学）
- Integer programs with bounded subdeterminants and two nonzeros per row
日本大学: 関与なし（対象大学）
- LEARN-Uniform Circuit Lower Bounds and Provability in Bounded Arithmetic
日本大学: 関与なし（対象大学）
- Learning Deep ReLU Networks Is Fixed-Parameter Tractable
日本大学: 関与なし（対象大学）
- Linear Probing Revisited: Tombstones Mark the Demise of Primary Clustering
日本大学: 関与なし（対象大学）
- List-decodability with large radius for Reed-Solomon codes
日本大学: 関与なし（対象大学）
- MAJORITY-3SAT (and Related Problems) in Polynomial Time
日本大学: 関与なし（対象大学）
- Minimum Cuts in Directed Graphs via Partial Sparsification
日本大学: 関与なし（対象大学）
- Minor Sparsifiers and the Distributed Laplacian Paradigm
日本大学: 関与なし（対象大学）
- Multiway Online Correlated Selection
日本大学: 関与なし（対象大学）
- New data structure for univariate polynomial approximation and applications to root isolation, numerical multipoint evaluation, and other problems
日本大学: 関与なし（対象大学）
- Noise and the Frontier of Quantum Supremacy
日本大学: 関与なし（対象大学）
- Non-adaptive vs Adaptive Queries in the Dense Graph Testing Model
日本大学: 関与なし（対象大学）
- On Classifying Continuous Constraint Satisfaction problems
日本大学: 関与なし（対象大学）
- On Worst-Case Learning in Relativized Heuristica
日本大学: 東京科学大学
- On statistical inference when fixed points of belief propagation are unstable
日本大学: 関与なし（対象大学）
- On the Impossibility of Post-Quantum Black-Box Zero-Knowledge in Constant Round
日本大学: 関与なし（対象大学）
- On the Nisan-Ronen conjecture
日本大学: 関与なし（対象大学）
- On the Power of Preconditioning in Sparse Linear Regression
日本大学: 関与なし（対象大学）
- One-step replica symmetry breaking of random regular NAE-SAT
日本大学: 関与なし（対象大学）
- Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination
日本大学: 関与なし（対象大学）
- Optimal Approximate Distance Oracle for Planar Graphs
日本大学: 関与なし（対象大学）
- Optimal Sub-Gaussian Mean Estimation in $\mathbb{R}$
日本大学: 関与なし（対象大学）
- PPSZ is better than you think
日本大学: 関与なし（対象大学）
- Parameterized Problems Complete for Nondeterministic FPT time and Logarithmic Space
日本大学: 関与なし（対象大学）
- Post-Quantum Succinct Arguments: Breaking the Quantum Rewinding Barrier
日本大学: 関与なし（対象大学）
- Proof of the Contiguity Conjecture and Lognormal Limit for the Symmetric Perceptron
日本大学: 関与なし（対象大学）
- Properly learning decision trees in almost polynomial time
日本大学: 関与なし（対象大学）
- Quantum learning algorithms imply circuit lower bounds
日本大学: 関与なし（対象大学）
- Quantum soundness of testing tensor codes
日本大学: 関与なし（対象大学）
- Quantum supremacy and hardness of estimating output probabilities of quantum circuits
日本大学: 東京科学大学
- Quasi-polynomial Time Approximation of Output Probabilities of Geometrically-local, Shallow Quantum Circuits
日本大学: 関与なし（対象大学）
- Random Order Online Set Cover is as Easy as Offline
日本大学: 関与なし（対象大学）
- Random walks and forbidden minors III: $\text{poly}\left(d\varepsilon ^{-1}\right)$-time partition oracles for minor-free graph classes
日本大学: 関与なし（対象大学）
- Rapid mixing of Glauber dynamics via spectral independence for all degrees
日本大学: 関与なし（対象大学）
- Reachability in Vector Addition Systems is Ackermann-complete
日本大学: 関与なし（対象大学）
- Robust recovery for stochastic block models
日本大学: 関与なし（対象大学）
- SNARGs for $\mathcal{P}$ from LWE
日本大学: 関与なし（対象大学）
- Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learning
日本大学: 関与なし（対象大学）
- Sharp Thresholds in Random Simple Temporal Graphs
日本大学: 関与なし（対象大学）
- Sharper bounds on the Fourier concentration of DNFs
日本大学: 関与なし（対象大学）
- Small-space and streaming pattern matching with $k$ edits
日本大学: 関与なし（対象大学）
- Smoothed Analysis with Adaptive Adversaries
日本大学: 関与なし（対象大学）
- Spectral Hypergraph Sparsifiers of Nearly Linear Size
日本大学: 関与なし（対象大学）
- Spectral Independence via Stability and Applications to Holant-Type Problems
日本大学: 関与なし（対象大学）
- Statistically Near-Optimal Hypothesis Selection
日本大学: 関与なし（対象大学）
- Stochastic and Worst-Case Generalized Sorting Revisited
日本大学: 関与なし（対象大学）
- Sum-of-Squares Lower Bounds for Sparse Independent Set
日本大学: 豊田工業大学