Conferences · eligible papers
SODA
2022–2026 LIVE
2026 · 243 papers
このEditionに反映済みのmain full research papersのみ掲載しています。著者リンクは日本の大学への著者別所属根拠がある場合に限ります。
- #CFG and #DNNF admit FPRAS
日本大学: 関与なし（対象大学）
- (Almost) Perfect Discrete Iterative Load Balancing
日本大学: 関与なし（対象大学）
- A Better-Than-2 Approximation for the Directed Tree Augmentation Problem
日本大学: 関与なし（対象大学）
- A Better-Than-5/4-Approximation for Two-Edge Connectivity
日本大学: 関与なし（対象大学）
- A Broader View on Clustering under Cluster-Aware Norm Objectives
日本大学: 関与なし（対象大学）
- A CSP approach to Graph Sandwich Problems
日本大学: 関与なし（対象大学）
- A Classical Quadratic Speedup for Planted \(k\) <scp>xor</scp>
日本大学: 関与なし（対象大学）
- A Classification of Long-Refinement Graphs for Colour Refinement
日本大学: 関与なし（対象大学）
- A Deterministic Polylogarithmic Competitive Algorithm for Matching with Delays
日本大学: 関与なし（対象大学）
- A Few Good Choices
日本大学: 関与なし（対象大学）
- A Logic-based Algorithmic Meta-Theorem for Treedepth: Single Exponential FPT Time and Polynomial Space
日本大学: 関与なし（対象大学）
- A Near-Complete Resolution of the Exponential-Time Complexity of \(k\)-opt for the Traveling Salesman Problem
日本大学: 関与なし（対象大学）
- A Post-Quantum Lower Bound for the Distributed Lovasz Local Lemma
日本大学: 関与なし（対象大学）
- A Truly Subcubic Combinatorial Algorithm for Induced 4-Cycle Detection
日本大学: 関与なし（対象大学）
- A Tutte-type canonical decomposition of 3- and 4-connected graphs
日本大学: 関与なし（対象大学）
- A \((2 + \varepsilon)\)-approximation algorithm for the general scheduling problem in quasipolynomial time
日本大学: 関与なし（対象大学）
- A near-optimal quadratic Goldreich-Levin algorithm (extended abstract)
日本大学: 関与なし（対象大学）
- A parameterized linear formulation of the integer hull
日本大学: 関与なし（対象大学）
- A quasi-polynomial bound for the minimal excluded minors for a surface
日本大学: 東京大学
- A well-separated pair decomposition for low density graphs
日本大学: 関与なし（対象大学）
- Additive Approximation Schemes for Low-Dimensional Embeddings
日本大学: 関与なし（対象大学）
- Algebraic Closure of Matrix Sets Recognized by 1-VASS
日本大学: 関与なし（対象大学）
- Algorithmic Improvements to List Decoding of Folded Reed-Solomon Codes
日本大学: 関与なし（対象大学）
- Algorithms and Lower Bounds for the Maximum Overlap of Two Polygons Under Translation
日本大学: 関与なし（対象大学）
- All-Pairs Minimum Cut using \(\tilde O(n^{7/4})\) Cut Queries
日本大学: 関与なし（対象大学）
- An Efficient Massively Parallel Constant-Factor Approximation Algorithm for the \(k\)-Means Problem
日本大学: 関与なし（対象大学）
- An Optimal Density Bound for Discretized Point Patrolling
日本大学: 関与なし（対象大学）
- An Optimal Online Algorithm for Robust Flow Time Scheduling
日本大学: 関与なし（対象大学）
- An Unconditional Lower Bound for the Active-Set Method in Convex Quadratic Maximization
日本大学: 関与なし（対象大学）
- An optimal algorithm for average distance in typical regular graphs
日本大学: 関与なし（対象大学）
- Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure
日本大学: 関与なし（対象大学）
- Approximate Counting of Permutation Patterns
日本大学: 関与なし（対象大学）
- Approximate Light Spanners in Planar Graphs
日本大学: 関与なし（対象大学）
- Approximately Dominating Sets in Elections
日本大学: 関与なし（対象大学）
- Approximating Asymmetric A Priori TSP beyond the Adaptivity Gap
日本大学: 関与なし（対象大学）
- Approximating Matroid Basis Testing for Partition Matroids using Budget-In-Expectation
日本大学: 関与なし（対象大学）
- Augmenting Packing Dynamic Programs to Handle (Many) Additional Budget Constraints
日本大学: 関与なし（対象大学）
- Augmenting to 4-vertex connectivity is fixed-parameter tractable
日本大学: 関与なし（対象大学）
- Balanced Spanning Tree Distributions Have Separation Fairness
日本大学: 関与なし（対象大学）
- Balls and Bins and the Infinite Process with Random Deletions
日本大学: 関与なし（対象大学）
- Beating full state tomography for unentangled spectrum estimation
日本大学: 関与なし（対象大学）
- Better Bounds for Semi-Streaming Single-Source Shortest Paths
日本大学: 関与なし（対象大学）
- Better Regret Rates in Bilateral Trade via Sublinear Budget Violation
日本大学: 関与なし（対象大学）
- Bounding the asymptotic quantum value of all multipartite compiled non-local games
日本大学: 関与なし（対象大学）
- Braiding Vineyards
日本大学: 関与なし（対象大学）
- Breaching the 2-Approximation Barrier for Euclidean Capacitated Vehicle Routing
日本大学: 関与なし（対象大学）
- Burling Graphs in Graphs with Large Chromatic Number
日本大学: 関与なし（対象大学）
- Catching Rats in \(H\)-minor-free Graphs
日本大学: 関与なし（対象大学）
- Cell-Probe Lower Bounds via Semi-Random CSP Refutation: Simplified and the Odd-Locality Case
日本大学: 関与なし（対象大学）
- Centered colorings in minor-closed graph classes
日本大学: 関与なし（対象大学）
- Circuits and Backdoors: Five Shades of the SETH
日本大学: 関与なし（対象大学）
- Collaborative Prediction: Tractable Information Aggregation via Agreement
日本大学: 関与なし（対象大学）
- Coloring 3-Colorable Graphs with Low Threshold Rank
日本大学: 関与なし（対象大学）
- Coloring Graphs with Few Colors in the Streaming Model
日本大学: 関与なし（対象大学）
- Combinatorial Philosopher Inequalities
日本大学: 関与なし（対象大学）
- Combinatorial Selection with Costly Information
日本大学: 関与なし（対象大学）
- Comparison Theorems for the Mixing Times of Systematic and Random Scan Dynamics
日本大学: 関与なし（対象大学）
- Compatibility of Fairness and Nash Welfare under Subadditive Valuations
日本大学: 関与なし（対象大学）
- Computational Complexity in Property Testing
日本大学: 関与なし（対象大学）
- Computational barriers for permutation-based problems, and cumulants of weakly dependent random variables
日本大学: 関与なし（対象大学）
- Computing the Heaviest Disk and Related Problems
日本大学: 関与なし（対象大学）
- Contextual Search in Principal-Agent Games: The Curse of Degeneracy
日本大学: 関与なし（対象大学）
- Contract Design Beyond Hidden-Actions
日本大学: 関与なし（対象大学）
- Contract Design for Sequential Actions
日本大学: 関与なし（対象大学）
- Covering the Euclidean Plane by a Pair of Trees
日本大学: 関与なし（対象大学）
- Derandomizing Pseudopolynomial Algorithms for Subset Sum
日本大学: 関与なし（対象大学）
- Detecting Correlation Efficiently in Very Supercritical Stochastic Block Models: Breaking the Otter’s Threshold Barrier
日本大学: 関与なし（対象大学）
- Deterministic Dynamic Edge Colouring
日本大学: 関与なし（対象大学）
- Deterministic and Exact Fully-dynamic Minimum Cut of Superpolylogarithmic Size in Subpolynomial Time
日本大学: 関与なし（対象大学）
- Determinization of Min-Plus Weighted Automata is Decidable
日本大学: 関与なし（対象大学）
- Dichotomy for orderings?
日本大学: 関与なし（対象大学）
- Differentially Private Algorithms for Graph Cuts: A Shifting Mechanism Approach and More
日本大学: 関与なし（対象大学）
- Differentially Private Quasi-Concave Optimization: Bypassing the Lower Bound and Application to Geometric Problems
日本大学: 関与なし（対象大学）
- Disjoint Paths in Expanders in Deterministic Almost-Linear Time via Hypergraph Perfect Matching
日本大学: 関与なし（対象大学）
- Distributed Interactive Proofs for Planarity with Log-Star Communication
日本大学: 関与なし（対象大学）
- Distributed Quantum Advantage in Locally Checkable Labeling Problems
日本大学: 関与なし（対象大学）
- Distribution Testing in the Presence of Arbitrarily Dominant Noise with Verification Queries
日本大学: 関与なし（対象大学）
- Does block size matter in randomized block Krylov low-rank approximation?
日本大学: 関与なし（対象大学）
- Downward self-reducibility in the total function polynomial hierarchy
日本大学: 関与なし（対象大学）
- Dynamic Connectivity with Expected Polylogarithmic Worst-Case Update Time
日本大学: 関与なし（対象大学）
- Dynamic Hierarchical j-Tree Decomposition and Its Applications
日本大学: 関与なし（対象大学）
- Efficient Online Random Sampling via Randomness Recycling
日本大学: 関与なし（対象大学）
- Efficiently Constructing Sparse Navigable Graphs
日本大学: 関与なし（対象大学）
- Entrywise Approximation for Matrix Inversion and Linear Systems
日本大学: 関与なし（対象大学）
- Evasive sets, twisted varieties, and container-clique trees
日本大学: 関与なし（対象大学）
- Excluding a Line Minor via Design Matrices and Column Number Bounds for the Circuit Imbalance Measure
日本大学: 関与なし（対象大学）
- Existence of Fair and Efficient Allocation of Indivisible Chores
日本大学: 東京大学
- Expander Pruning with Polylogarithmic Worst-Case Recourse and Update Time
日本大学: 関与なし（対象大学）
- Explaining the Inherent Tradeoffs for Suffix Array Functionality: Equivalences between String Problems and Prefix Range Queries
日本大学: 関与なし（対象大学）
- Explicit Min-wise Hash Families with Optimal Size
日本大学: 関与なし（対象大学）
- Extended VC-dimension, and Radon and Tverberg type theorems for unions of convex sets
日本大学: 関与なし（対象大学）
- Fair Division Beyond Monotone Valuations with Applications to Equitable Graph Partitioning
日本大学: 関与なし（対象大学）
- Faster Algorithms for Global Minimum Vertex-Cut in Directed Graphs
日本大学: 関与なし（対象大学）
- Faster Distributed \(\Delta\)-Coloring via a Reduction to MIS
日本大学: 関与なし（対象大学）
- Faster Estimation of the Average Degree of a Graph Using Random Edges and Structural Queries
日本大学: 関与なし（対象大学）
- Faster Negative-Weight Shortest Paths and Directed Low-Diameter Decompositions
日本大学: 関与なし（対象大学）
- Faster algorithms for packing forests in graphs and related problems
日本大学: 関与なし（対象大学）
- Faster negative length shortest paths by bootstrapping hop reducers
日本大学: 関与なし（対象大学）
- Feature Selection and Junta Testing are Statistically Equivalent
日本大学: 関与なし（対象大学）
- Finding sparse induced subgraphs on graphs of bounded induced matching treewidth
日本大学: 関与なし（対象大学）