Conferences · eligible papers
FOCS
2022–2026 LIVE
2022 · 110 papers
このEditionに反映済みのmain full research papersのみ掲載しています。著者リンクは日本の大学への著者別所属根拠がある場合に限ります。
- A (Slightly) Improved Bound on the Integrality Gap of the Subtour LP for TSP
日本大学: 関与なし（対象大学）
- A Characterization of Multiclass Learnability
日本大学: 関与なし（対象大学）
- A Hash Table Without Hash Functions, and How to Get the Most Out of Your Random Bits
日本大学: 関与なし（対象大学）
- A Proof of the Kahn-Kalai Conjecture
日本大学: 関与なし（対象大学）
- A tight (non-combinatorial) conditional lower bound for Klee’s Measure Problem in 3D
日本大学: 関与なし（対象大学）
- Active Linear Regression for ℓp Norms and Beyond
日本大学: 関与なし（対象大学）
- Algorithms and Barriers in the Symmetric Binary Perceptron Model
日本大学: 関与なし（対象大学）
- Algorithms and Lower Bounds for Replacement Paths under Multiple Edge Failure
日本大学: 関与なし（対象大学）
- Algorithms for the ferromagnetic Potts model on expanders
日本大学: 関与なし（対象大学）
- Almost 3-Approximate Correlation Clustering in Constant Rounds
日本大学: 関与なし（対象大学）
- Almost Ramanujan Expanders from Arbitrary Expanders via Operator Amplification
日本大学: 関与なし（対象大学）
- An Approximate Generalization of the Okamura-Seymour Theorem
日本大学: 関与なし（対象大学）
- Approximation Algorithms and Hardness for n-Pairs Shortest Paths and All-Nodes Shortest Cycles
日本大学: 関与なし（対象大学）
- Balanced Allocations: The Heavily Loaded Case with Deletions
日本大学: 関与なし（対象大学）
- Binary Codes with Resilience Beyond 1/4 via Interaction
日本大学: 関与なし（対象大学）
- Binary Iterative Hard Thresholding Converges with Optimal Number of Measurements for 1-Bit Compressed Sensing
日本大学: 関与なし（対象大学）
- Breaking the Cubic Barrier for All-Pairs Max-Flow: Gomory-Hu Tree in Nearly Quadratic Time
日本大学: 関与なし（対象大学）
- Cheeger Inequalities for Vertex Expansion and Reweighted Eigenvalues
日本大学: 関与なし（対象大学）
- Classical Verification of Quantum Computations in Linear Time
日本大学: 関与なし（対象大学）
- Computing in Anonymous Dynamic Networks Is Linear
日本大学: 北陸先端科学技術大学院大学
- Constant Approximation of Min-Distances in Near-Linear Time
日本大学: 関与なし（対象大学）
- Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixtures
日本大学: 関与なし（対象大学）
- Correlation Clustering with Sherali-Adams
日本大学: 関与なし（対象大学）
- Cut Query Algorithms with Star Contraction
日本大学: 関与なし（対象大学）
- Derandomizing Directed Random Walks in Almost-Linear Time
日本大学: 関与なし（対象大学）
- Determinant Maximization via Matroid Intersection Algorithms
日本大学: 関与なし（対象大学）
- Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and Parallel Applications
日本大学: 関与なし（対象大学）
- Deterministic Small Vertex Connectivity in Almost Linear Time
日本大学: 関与なし（対象大学）
- Differential Privacy from Locally Adjustable Graph Algorithms: k-Core Decomposition, Low Out-Degree Ordering, and Densest Subgraphs
日本大学: 関与なし（対象大学）
- Error Correcting Codes that Achieve BSC Capacity Against Channels that are Poly-Size Circuits
日本大学: 関与なし（対象大学）
- Estimating the Longest Increasing Subsequence in Nearly Optimal Time
日本大学: 関与なし（対象大学）
- Explicit Lower Bounds Against Ω(n)-Rounds of Sum-of-Squares
日本大学: 関与なし（対象大学）
- Factorial Lower Bounds for (Almost) Random Order Streams
日本大学: 関与なし（対象大学）
- Fast Deterministic Fully Dynamic Distance Approximation
日本大学: 関与なし（対象大学）
- Fast Multivariate Multipoint Evaluation Over All Finite Fields
日本大学: 関与なし（対象大学）
- Faster Pattern Matching under Edit Distance : A Reduction to Dynamic Puzzle Matching and the Seaweed Monoid of Permutation Matrices
日本大学: 関与なし（対象大学）
- First Price Auction is 1 – 1 /e2 Efficient
日本大学: 関与なし（対象大学）
- Fitting Metrics and Ultrametrics with Minimum Disagreements
日本大学: 関与なし（対象大学）
- Fooling polynomials using invariant theory
日本大学: 関与なし（対象大学）
- Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal
日本大学: 関与なし（対象大学）
- Generalised entropy accumulation
日本大学: 関与なし（対象大学）
- Geometry of Secure Two-party Computation
日本大学: 関与なし（対象大学）
- Hardness Self-Amplification from Feasible Hard-Core Sets
日本大学: 東京科学大学
- Having Hope in Hops: New Spanners, Preservers and Lower Bounds for Hopsets
日本大学: 関与なし（対象大学）
- High-Dimensional Geometric Streaming in Polynomial Space
日本大学: 関与なし（対象大学）
- Improved Lower Bounds for Submodular Function Minimization
日本大学: 関与なし（対象大学）
- Improved Optimal Testing Results from Global Hypercontractivity
日本大学: 関与なし（対象大学）
- Inapproximability of Positive Semidefinite Permanents and Quantum State Tomography
日本大学: 関与なし（対象大学）
- Incrementally Verifiable Computation via Rate-1 Batch Arguments
日本大学: 関与なし（対象大学）
- Indistinguishability Obfuscation via Mathematical Proofs of Equivalence
日本大学: 関与なし（対象大学）
- Induced Cycles and Paths Are Harder Than You Think
日本大学: 関与なし（対象大学）
- Interior point methods are not worse than Simplex
日本大学: 関与なし（対象大学）
- Killing a vortex
日本大学: 関与なし（対象大学）
- Linear Hashing with ℓ∞ guarantees and two-sided Kakeya bounds
日本大学: 関与なし（対象大学）
- Local Computation of Maximal Independent Set
日本大学: 関与なし（対象大学）
- Localization Schemes: A Framework for Proving Mixing Bounds for Markov Chains (extended abstract)
日本大学: 関与なし（対象大学）
- Low Treewidth Embeddings of Planar and Minor-Free Metrics
日本大学: 関与なし（対象大学）
- Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
日本大学: 関与なし（対象大学）
- Memory Bounds for Continual Learning
日本大学: 関与なし（対象大学）
- Minimax Rates for Robust Community Detection
日本大学: 関与なし（対象大学）
- Motif Cut Sparsifiers
日本大学: 関与なし（対象大学）
- NP-Hardness of Learning Programs and Partial MCSP
日本大学: 関与なし（対象大学）
- Near-Optimal Deterministic Vertex-Failure Connectivity Oracles
日本大学: 関与なし（対象大学）
- Nearly Optimal Communication and Query Complexity of Bipartite Matching
日本大学: 関与なし（対象大学）
- Negative-Weight Single-Source Shortest Paths in Near-linear Time
日本大学: 関与なし（対象大学）
- New Additive Spanner Lower Bounds by an Unlayered Obstacle Product
日本大学: 関与なし（対象大学）
- On Bounded Depth Proofs for Tseitin Formulas on the Grid; Revisited
日本大学: 関与なし（対象大学）
- On Matrix Multiplication and Polynomial Identity Testing
日本大学: 関与なし（対象大学）
- On Weighted Graph Sparsification by Linear Sketching
日本大学: 関与なし（対象大学）
- On the Range Avoidance Problem for Circuits
日本大学: 関与なし（対象大学）
- Online List Labeling: Breaking the log2n Barrier
日本大学: 関与なし（対象大学）
- Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence
日本大学: 関与なし（対象大学）
- Optimal learning of quantum Hamiltonians from high-temperature Gibbs states
日本大学: 関与なし（対象大学）
- Optimal mixing for two-state anti-ferromagnetic spin systems
日本大学: 関与なし（対象大学）
- Order Selection Prophet Inequality: From Threshold Optimization to Arrival Time Design
日本大学: 関与なし（対象大学）
- Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models
日本大学: 関与なし（対象大学）
- Planting Undetectable Backdoors in Machine Learning Models : [Extended Abstract]
日本大学: 関与なし（対象大学）
- Polynomial-Time Power-Sum Decomposition of Polynomials
日本大学: 関与なし（対象大学）
- Post-Quantum Zero Knowledge, Revisited or: How to Do Quantum Rewinding Undetectably
日本大学: 関与なし（対象大学）
- Properly learning monotone functions via local correction
日本大学: 関与なし（対象大学）
- Punctured Low-Bias Codes Behave Like Random Linear Codes
日本大学: 関与なし（対象大学）
- Pure-Circuit: Strong Inapproximability for PPAD
日本大学: 関与なし（対象大学）
- Quantum Tanner codes
日本大学: 関与なし（対象大学）
- Radical Sylvester-Gallai Theorem for Cubics
日本大学: 関与なし（対象大学）
- Randomised Composition and Small-Bias Minimax
日本大学: 関与なし（対象大学）
- Rate-1 Non-Interactive Arguments for Batch-NP and Applications
日本大学: 関与なし（対象大学）
- Relaxed Locally Decodable and Correctable Codes: Beyond Tensoring
日本大学: 関与なし（対象大学）
- Rounds vs Communication Tradeoffs for Maximal Independent Sets
日本大学: 関与なし（対象大学）
- Sampling Lovász local lemma for general constraint satisfaction solutions in near-linear time
日本大学: 関与なし（対象大学）
- Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization
日本大学: 関与なし（対象大学）
- Separated borders: Exponential-gap fanin-hierarchy theorem for approximative depth-3 circuits
日本大学: 関与なし（対象大学）
- Separations in Proof Complexity and TFNP
日本大学: 関与なし（対象大学）
- Shortest Paths without a Map, but with an Entropic Regularizer
日本大学: 関与なし（対象大学）
- Simple Hard Instances for Low-Depth Algebraic Proofs
日本大学: 関与なし（対象大学）
- Solving SDP Faster: A Robust IPM Framework and Efficient Implementation
日本大学: 関与なし（対象大学）
- Solving the Hamilton cycle problem fast on average
日本大学: 関与なし（対象大学）
- Sparse random hypergraphs: Non-backtracking spectra and community detection
日本大学: 関与なし（対象大学）
- Streaming Facility Location in High Dimension via Geometric Hashing
日本大学: 関与なし（対象大学）
- Strong XOR Lemma for Communication with Bounded Rounds : (extended abstract)
日本大学: 関与なし（対象大学）
- Survivable Network Design Revisited: Group-Connectivity
日本大学: 関与なし（対象大学）