Conferences · eligible papers
SODA
2022–2026 LIVE
2025 · 192 papers
このEditionに反映済みのmain full research papersのみ掲載しています。著者リンクは日本の大学への著者別所属根拠がある場合に限ります。
- (Almost) Ruling Out SETH Lower Bounds for All-Pairs Max-Flow
日本大学: 関与なし（対象大学）
- A Cell Probe Lower Bound for the Predecessor Search Problem in PRAM
日本大学: 関与なし（対象大学）
- A Cut-Matching Game for Constant-Hop Expanders
日本大学: 関与なし（対象大学）
- A Dichotomy Hierarchy for Linear Time Subgraph Counting in Bounded Degeneracy Graphs
日本大学: 関与なし（対象大学）
- A Discrete Analog of Tutte’s Barycentric Embeddings on Surfaces
日本大学: 関与なし（対象大学）
- A Fast Algorithm for Computing Zigzag Representatives
日本大学: 関与なし（対象大学）
- A Lower Bound for Light Spanners in General Graphs
日本大学: 関与なし（対象大学）
- A Multi-Dimensional Online Contention Resolution Scheme for Revenue Maximization
日本大学: 関与なし（対象大学）
- A Polylogarithmic Approximation for Directed Steiner Forest in Planar Digraphs
日本大学: 関与なし（対象大学）
- A Quantum Speed-Up for Approximating the Top Eigenvectors of a Matrix
日本大学: 関与なし（対象大学）
- A Reduction from Multi-Parameter to Single-Parameter Bayesian Contract Design
日本大学: 関与なし（対象大学）
- A Refutation of the Pach-Tardos Conjecture for 0-1 Matrices
日本大学: 関与なし（対象大学）
- A Subexponential Time Algorithm for Makespan Scheduling of Unit Jobs with Precedence Constraints
日本大学: 関与なし（対象大学）
- A Sublinear-Time Algorithm for Nearly-Perfect Matchings in Regular Non-Bipartite Graphs
日本大学: 関与なし（対象大学）
- A Tight (3/2 + <i>∈</i> )-Approximation Algorithm for Demand Strip Packing
日本大学: 関与なし（対象大学）
- A Tight VC-Dimension Analysis of Clustering Coresets with Applications
日本大学: 関与なし（対象大学）
- A coarse Erdős-Pósa theorem
日本大学: 関与なし（対象大学）
- A topological proof of the Hell-Nešetřil dichotomy
日本大学: 関与なし（対象大学）
- All-Hops Shortest Paths
日本大学: 関与なし（対象大学）
- Almost Tight Bounds for Differentially Private Densest Subgraph
日本大学: 関与なし（対象大学）
- An Efficient Regularity Lemma for Semi-Algebraic Hypergraphs
日本大学: 関与なし（対象大学）
- An Efficient Uniqueness Theorem for Overcomplete Tensor Decomposition
日本大学: 関与なし（対象大学）
- An Elementary Predictor Obtaining Distance to Calibration
日本大学: 関与なし（対象大学）
- An analogue of Reed’s conjecture for digraphs
日本大学: 東京大学
- Approximately Counting Knapsack Solutions in Subquadratic Time
日本大学: 関与なし（対象大学）
- Approximating Competitive Equilibrium by Nash Welfare
日本大学: 関与なし（対象大学）
- Approximating Traveling Salesman Problems Using a Bridge Lemma
日本大学: 関与なし（対象大学）
- Approximating Unrelated Machine Weighted Completion Time Using Iterative Rounding and Computer Assisted Proofs
日本大学: 関与なし（対象大学）
- Asynchronous 3-Majority Dynamics with Many Opinions
- Average-Case Hardness of Parity Problems: Orthogonal Vectors, k-SUM and More
日本大学: 関与なし（対象大学）
- Balancing Notions of Equity: Trade-offs Between Fair Portfolio Sizes and Achievable Guarantees
日本大学: 関与なし（対象大学）
- Beating Bellman’s Algorithm for Subset Sum
日本大学: 関与なし（対象大学）
- Beyond 2-Approximation for <i>k</i> -Center in Graphs
日本大学: 関与なし（対象大学）
- Bounding <i>ε</i> -scatter dimension via metric sparsity
日本大学: 関与なし（対象大学）
- Breaking the Two Approximation Barrier for Various Consensus Clustering Problems
日本大学: 関与なし（対象大学）
- Certificates in P and Subquadratic-Time Computation of Radius, Diameter, and all Eccentricities in Graphs
日本大学: 関与なし（対象大学）
- Clock Auctions Augmented with Unreliable Advice
日本大学: 関与なし（対象大学）
- Clustering Mixtures of Bounded Covariance Distributions Under Optimal Separation
日本大学: 関与なし（対象大学）
- Clustering to Minimize Cluster-Aware Norm Objectives
日本大学: 関与なし（対象大学）
- Competitive strategies to use “warm start” algorithms with predictions
日本大学: 関与なし（対象大学）
- Complexity of polytope diameters via perfect matchings
日本大学: 関与なし（対象大学）
- Computing the second and third systoles of a combinatorial surface
日本大学: 関与なし（対象大学）
- Congestion-Approximators from the Bottom Up
日本大学: 関与なし（対象大学）
- Connectivity Labeling Schemes for Edge and Vertex Faults via Expander Hierarchies
日本大学: 関与なし（対象大学）
- Constraint Satisfaction Problems with Advice
日本大学: 関与なし（対象大学）
- Coresets for Constrained Clustering: General Assignment Constraints and Improved Size Bounds
日本大学: 関与なし（対象大学）
- Counting Small Induced Subgraphs: Hardness via Fourier Analysis
日本大学: 関与なし（対象大学）
- Crossing Number in Slightly Superexponential Time (Extended Abstract)
日本大学: 関与なし（対象大学）
- Designing Automated Market Makers for Combinatorial Securities: A Geometric Viewpoint
日本大学: 関与なし（対象大学）
- Deterministic Edge Connectivity and Max Flow using Subquadratic Cut Queries
日本大学: 関与なし（対象大学）
- Deterministic Online Bipartite Edge Coloring
日本大学: 関与なし（対象大学）
- Differentiable Approximations for Distance Queries
日本大学: 関与なし（対象大学）
- Dynamic Consistent <i>k</i> -Center Clustering with Optimal Recourse
日本大学: 関与なし（対象大学）
- Efficient <i>d</i> -ary Cuckoo Hashing at High Load Factors by Bubbling Up
日本大学: 関与なし（対象大学）
- Efficient Approximation Algorithm for Computing Wasserstein Barycenter under Euclidean Metric
日本大学: 関与なし（対象大学）
- Embedding Planar Graphs into Graphs of Treewidth <i>O</i> (log <sup>3</sup> <i>n</i> )
日本大学: 関与なし（対象大学）
- Embedding Probability Distributions into Low Dimensional ℓ <sub>1</sub> : Tree Ising Models via Truncated Metrics
日本大学: 関与なし（対象大学）
- Entropy Regularization and Faster Decremental Matching in General Graphs
日本大学: 関与なし（対象大学）
- Eulerian Graph Sparsification by Effective Resistance Decomposition
日本大学: 関与なし（対象大学）
- Even Faster (Δ + 1)-Edge Coloring via Shorter Multi-Step Vizing Chains
日本大学: 関与なし（対象大学）
- Exact Thresholds for Noisy Non-Adaptive Group Testing
日本大学: 関与なし（対象大学）
- FPTAS for Holant Problems with Log-Concave Signatures
日本大学: 関与なし（対象大学）
- Facet-Hamiltonicity
日本大学: 関与なし（対象大学）
- Fast Deterministic Chromatic Number under the Asymptotic Rank Conjecture
日本大学: 関与なし（対象大学）
- Fast Static and Dynamic Approximation Algorithms for Geometric Optimization Problems: Piercing, Independent Set, Vertex Cover, and Matching
日本大学: 関与なし（対象大学）
- Fast and Simple Sorting Using Partial Information
日本大学: 関与なし（対象大学）
- Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs
日本大学: 関与なし（対象大学）
- Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning
日本大学: 関与なし（対象大学）
- Faster Vizing and Near-Vizing Edge Coloring Algorithms
日本大学: 関与なし（対象大学）
- Faster single-source shortest paths with negative real weights via proper hop distance
日本大学: 関与なし（対象大学）
- Faster two-dimensional pattern matching with <i>k</i> mismatches
日本大学: 関与なし（対象大学）
- Finding irrelevant vertices in linear time on bounded-genus graphs
日本大学: 関与なし（対象大学）
- Fine-Grained Optimality of Partially Dynamic Shortest Paths and More
日本大学: 関与なし（対象大学）
- Fixed-Parameter Tractability of Hedge Cut
日本大学: 関与なし（対象大学）
- Flip Dynamics for Sampling Colorings: Improving (11/6 — ε) Using A Simple Metric
日本大学: 関与なし（対象大学）
- Flipping Non-Crossing Spanning Trees
日本大学: 関与なし（対象大学）
- Forall-exist statements in pseudopolynomial time
日本大学: 関与なし（対象大学）
- From Graph Properties to Graph Parameters: Tight Bounds for Counting on Small Subgraphs
日本大学: 総合研究大学院大学
- Fréchet Distance in Subquadratic Time
日本大学: 関与なし（対象大学）
- Fully Dynamic (Δ + 1)-Coloring Against Adaptive Adversaries
日本大学: 関与なし（対象大学）
- Fully Dynamic Algorithms for Graph Spanners via Low-Diameter Router Decomposition
日本大学: 関与なし（対象大学）
- Fully Dynamic Approximate Minimum Cut in Subpolynomial Time per Operation
日本大学: 関与なし（対象大学）
- Fully-Distributed Byzantine Agreement in Sparse Networks
日本大学: 関与なし（対象大学）
- Gains-from-Trade in Bilateral Trade with a Broker
日本大学: 関与なし（対象大学）
- Having Hope in Missing Spanners: New Distance Preservers and Light Hopsets
日本大学: 関与なし（対象大学）
- Hermitian Diagonalization in Linear Precision
日本大学: 関与なし（対象大学）
- Highway Dimension: a Metric View
日本大学: 関与なし（対象大学）
- Hiring for An Uncertain Task: Joint Design of Information and Contracts
日本大学: 関与なし（対象大学）
- Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemerédi Graphs
日本大学: 関与なし（対象大学）
- Improved Differentially Private Continual Observation Using Group Algebra
日本大学: 関与なし（対象大学）
- Improved Explicit Near-Optimal Codes in the High-Noise Regimes
日本大学: 関与なし（対象大学）
- Improved List Size for Folded Reed-Solomon Codes
日本大学: 関与なし（対象大学）
- Improved Online Reachability Preservers
日本大学: 関与なし（対象大学）
- Improved Shortest Path Restoration Lemmas for Multiple Edge Failures: Trade-offs Between Fault-tolerance and Subpaths
日本大学: 関与なし（対象大学）
- Improved Spectral Density Estimation via Explicit and Implicit Deflation
日本大学: 関与なし（対象大学）
- Improving the Leading Constant of Matrix Multiplication
日本大学: 関与なし（対象大学）
- Inapproximability of Maximum Diameter Clustering for Few Clusters
日本大学: 関与なし（対象大学）
- Integer programs with nearly totally unimodular matrices: the cographic case
日本大学: 関与なし（対象大学）
- Lift-and-Project Integrality Gaps for Santa Claus
日本大学: 関与なし（対象大学）
- Linear equations with monomial constraints and decision problems in abelian-by-cyclic groups
日本大学: 関与なし（対象大学）