Conferences · eligible papers
SODA
2022–2026 LIVE
2026 · 243 papers
このEditionに反映済みのmain full research papersのみ掲載しています。著者リンクは日本の大学への著者別所属根拠がある場合に限ります。
- Finite Pinwheel Scheduling: the \(\text{k}\)-Visits Problem
日本大学: 関与なし（対象大学）
- From Incremental Transitive Cover to Strongly Polynomial Maximum Flow
日本大学: 関与なし（対象大学）
- From Unweighted to Weighted Dynamic Matching in Non-Bipartite Graphs: A Low-Loss Reduction
日本大学: 関与なし（対象大学）
- Generating pivot Gray codes for spanning trees of complete graphs in constant amortized time
日本大学: 関与なし（対象大学）
- Halfspaces are hard to test with relative error
日本大学: 関与なし（対象大学）
- Hallucinating Flows for Optimal Mechanisms
日本大学: 関与なし（対象大学）
- Hardness of Approximation for Shortest Path with Vector Costs
日本大学: 関与なし（対象大学）
- Helly-Type Theorems for Splitting Point Sets
日本大学: 関与なし（対象大学）
- History-Independent Load Balancing
日本大学: 関与なし（対象大学）
- History-Independent Maximal Matchings can be Surprisingly Efficient, and Lead to Better Worst-Case Guarantees
日本大学: 関与なし（対象大学）
- Improved Additive Approximation Algorithms for APSP
日本大学: 関与なし（対象大学）
- Improved Approximation for Ranking on General Graphs
日本大学: 関与なし（対象大学）
- Improved Maximin Share Guarantee for Additive Valuations
日本大学: 関与なし（対象大学）
- Improved Online Algorithms for Inventory Management Problems with Holding and Delay Costs: Riding the Wave Makes Things Simpler, Stronger, & More General
日本大学: 関与なし（対象大学）
- Improving Algorithmic Efficiency using Cryptography: Trapdoored Matrices and Applications
日本大学: 関与なし（対象大学）
- Interaction Between Skew-representability, Tensor Products, Extension Properties, and Rank Inequalities
日本大学: 関与なし（対象大学）
- Is nasty noise actually harder than malicious noise?
日本大学: 関与なし（対象大学）
- Language Generation in the Limit: Noise, Loss, and Feedback
日本大学: 関与なし（対象大学）
- Learning Packing and Covering from Samples
日本大学: 関与なし（対象大学）
- Learning in an Echo Chamber: Online Learning with Replay Adversary
日本大学: 関与なし（対象大学）
- Likelihood of the Existence of Average Justified Representation
日本大学: 関与なし（対象大学）
- Listing faces of polytopes
日本大学: 関与なし（対象大学）
- Local Gibbs sampling beyond local uniformity
日本大学: 関与なし（対象大学）
- Local Search for Clustering in Almost-linear Time
日本大学: 関与なし（対象大学）
- Long Arithmetic Progressions in Sparse Subset Sums: A Computational Perspective
日本大学: 関与なし（対象大学）
- Low-Sensitivity Matching via Sampling from Gibbs Distributions
日本大学: 関与なし（対象大学）
- Lower Bounds for CSP Hierarchies Through Ideal Reduction
日本大学: 関与なし（対象大学）
- Lower bounds for the universal TSP on the plane
日本大学: 関与なし（対象大学）
- MAX BISECTION might be harder to approximate than MAX CUT
日本大学: 関与なし（対象大学）
- Matroids are Equitable
日本大学: 関与なし（対象大学）
- Minimum \(s\!-\!t\) Cuts with Fewer Cut Queries
日本大学: 関与なし（対象大学）
- Near-Optimal Centerpoints in Polynomial Time in the Ambient Dimension
日本大学: 関与なし（対象大学）
- Near-Optimal Four-Cycle Counting in Graph Streams
日本大学: 関与なし（対象大学）
- Near-Optimal Min-Sum Multi-Robot Motion Planning in a Planar Polygonal Environment
日本大学: 関与なし（対象大学）
- Near-linear time subhypergraph counting in bounded degeneracy hypergraphs
日本大学: 関与なし（対象大学）
- Nearly Optimal Bounds for Stochastic Online Sorting
日本大学: 関与なし（対象大学）
- Nearly Tight Bounds for the Online Sorting Problem
日本大学: 関与なし（対象大学）
- Nearly Tight Sample Complexity for Matroid Online Contention Resolution
日本大学: 関与なし（対象大学）
- Networked Information Aggregation via Machine Learning
日本大学: 関与なし（対象大学）
- New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs
日本大学: 関与なし（対象大学）
- New Oracles and Labeling Schemes for Vertex Cut Queries
日本大学: 関与なし（対象大学）
- Numerical Linear Algebra in Linear Space
日本大学: 関与なし（対象大学）
- On Deterministically Finding an Element of High Order Modulo a Composite
日本大学: 関与なし（対象大学）
- On Distributed Colouring of Hyperbolic Random Graphs
日本大学: 関与なし（対象大学）
- On Independent Spanning Trees in Random Graphs
日本大学: 関与なし（対象大学）
- On Lines Crossing Pairwise Intersecting Convex Sets in Three Dimensions
日本大学: 関与なし（対象大学）
- On a Clique Game and the Erdős-Hajnal Problem on High-Chromatic High-Girth Subgraphs
日本大学: 関与なし（対象大学）
- On sampling two spin models using the local connective constant
日本大学: 関与なし（対象大学）
- On the Complexity of the Skolem Problem at Low Orders
日本大学: 関与なし（対象大学）
- On the Computation of Schrijver’s Kernels
日本大学: 関与なし（対象大学）
- On the Quantum Chromatic Gap
日本大学: 関与なし（対象大学）
- On the Structure of Replicable Hypothesis Testers
日本大学: 関与なし（対象大学）
- On the Universality of Round Elimination Fixed Points
日本大学: 関与なし（対象大学）
- On the Usefulness of Promises
日本大学: 関与なし（対象大学）
- On the edge expansion of random polytopes
日本大学: 関与なし（対象大学）
- One Attack to Rule Them All: Tight Quadratic Bounds for Adaptive Queries on Cardinality Sketches
日本大学: 関与なし（対象大学）
- Online 3-Taxi on General Metrics
日本大学: 関与なし（対象大学）
- Online Conformal Prediction with Efficiency Guarantees
日本大学: 関与なし（対象大学）
- Online Connectivity Augmentation
日本大学: 関与なし（対象大学）
- Online Joint Replenishment Problem with Arbitrary Holding and Backlog Costs
日本大学: 関与なし（対象大学）
- Online Learning with Limited Information in the Sliding Window Model
日本大学: 関与なし（対象大学）
- Online Orthogonal Vectors Revisited
日本大学: 関与なし（対象大学）
- Online Proportional Apportionment
日本大学: 関与なし（対象大学）
- Online Resource Allocation with Concave, Diminishing-Returns Objectives
日本大学: 関与なし（対象大学）
- Optimal Random Access and Conditional Lower Bounds for 2D Compressed Strings
日本大学: 関与なし（対象大学）
- Optimal Rounding for Two-Stage Bipartite Matching
日本大学: 関与なし（対象大学）
- Optimal Subspace Embeddings: Resolving Nelson-Nguyen Conjecture Up to Sub-Polylogarithmic Factors
日本大学: 関与なし（対象大学）
- Optimal Type-Dependent Liquid Welfare Guarantees for Autobidding Agents with Budgets
日本大学: 関与なし（対象大学）
- Optimal mass estimation in the conditional sampling model
日本大学: 関与なし（対象大学）
- Optimal randomized clustering for subsets of \(L_p\) when \(p \gt 2\)
日本大学: 関与なし（対象大学）
- Optimization Modulo Integer Linear-Exponential Programs
日本大学: 関与なし（対象大学）
- PageRank Centrality in Directed Graphs with Bounded In-Degree
日本大学: 関与なし（対象大学）
- Peeling Rotten Potatoes for a Faster Approximation of Convex Cover
日本大学: 関与なし（対象大学）
- Perfect Matchings in Random Sparsifications of Dense Hypergraphs
日本大学: 関与なし（対象大学）
- Persuasive Calibration
日本大学: 関与なし（対象大学）
- Phase transition of the Sinkhorn-Knopp algorithm
日本大学: 関与なし（対象大学）
- Planar Disjoint Shortest Paths is Fixed-Parameter Tractable
日本大学: 関与なし（対象大学）
- Plane vs. Plane Low Degree Test
日本大学: 関与なし（対象大学）
- Polynomial-Time Classical Simulation of Noisy Quantum Circuits with Naturally Fault-Tolerant Gates
日本大学: 関与なし（対象大学）
- Problems from Optimization and Computational Algebra Equivalent to Hilbert’s Nullstellensatz
日本大学: 関与なし（対象大学）
- Prophet Inequality from Samples: Is the More the Merrier?
日本大学: 関与なし（対象大学）
- Quantum Advantage via Solving Multivariate Polynomials
日本大学: 関与なし（対象大学）
- Quantum Hamiltonian Certification
日本大学: 関与なし（対象大学）
- Quantum State Preparation with Optimal T-Count
日本大学: 関与なし（対象大学）
- RETRACTED: A Simple and Fast Reduction from Gomory-Hu Trees to Polylog Maxflows
日本大学: 関与なし（対象大学）
- RETRACTED: Constructive \(\ell_2\)-Discrepancy Minimization with Additive Deviations
日本大学: 関与なし（対象大学）
- RETRACTED: Dynamic 3D Convex Hulls Revisited and Applications
日本大学: 関与なし（対象大学）
- Rapid Mixing of Glauber Dynamics for Monotone Systems via Entropic Independence
日本大学: 関与なし（対象大学）
- Rapid mixing for Gibbs states within a logical sector: a dynamical view of self-correcting quantum memories
日本大学: 関与なし（対象大学）
- Recognizing Leaf Powers and Pairwise Compatibility Graphs is NP-Complete
日本大学: 関与なし（対象大学）
- Robust Equilibria in Shared Resource Allocation via Strengthening Border’s Theorem
日本大学: 関与なし（対象大学）
- Rumour Spreading Depends on the Latent Geometry and Degree Distribution in Social Network Models
日本大学: 関与なし（対象大学）
- Sample-efficient Replicable Median in Polynomial Time
日本大学: 関与なし（対象大学）
- Selfish, Local and Online Scheduling via Vector Fitting
日本大学: 関与なし（対象大学）
- Sensitivity Lower Bounds for Approximation Algorithms
日本大学: 関与なし（対象大学）
- Separations between Oblivious and Adaptive Adversaries for Natural Dynamic Graph Problems
日本大学: 関与なし（対象大学）
- Short circuit walks in fixed dimension
日本大学: 関与なし（対象大学）
- Shortcuts and Transitive-Closure Spanners Approximation
日本大学: 関与なし（対象大学）
- Smooth Trade-off for Tensor PCA via Sharp Bounds for Kikuchi Matrices
日本大学: 関与なし（対象大学）
- Space-Efficient \(k\)-Mismatch Text Indexes
日本大学: 関与なし（対象大学）