Conferences · eligible papers
SODA
2022–2026 LIVE
2023 · 190 papers
このEditionに反映済みのmain full research papersのみ掲載しています。著者リンクは日本の大学への著者別所属根拠がある場合に限ります。
- 4D Range Reporting in the Pointer Machine Model in Almost-Optimal Time
日本大学: 関与なし（対象大学）
- A Distanced Matching Game, Decremental APSP in Expanders, and Faster Deterministic Algorithms for Graph Cut Problems
日本大学: 関与なし（対象大学）
- A Framework for Approximation Schemes on Disk Graphs
日本大学: 関与なし（対象大学）
- A Near-Linear Time Sampler for the Ising Model with External Field
日本大学: 関与なし（対象大学）
- A Nearly Tight Analysis of Greedy k-means++
日本大学: 関与なし（対象大学）
- A Nearly Time-Optimal Distributed Approximation of Minimum Cost <i>k</i> -Edge-Connected Spanning Subgraph
日本大学: 関与なし（対象大学）
- A Nearly-Tight Analysis of Multipass Pairing Heaps
日本大学: 関与なし（対象大学）
- A New Approach to Estimating Effective Resistances and Counting Spanning Trees in Expander Graphs
日本大学: 関与なし（対象大学）
- A Polynomial Time Algorithm for Finding a Minimum 4-Partition of a Submodular Function
日本大学: 京都大学
- A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games
日本大学: 関与なし（対象大学）
- A Sublinear-Time Quantum Algorithm for Approximating Partition Functions
日本大学: 関与なし（対象大学）
- A Subquadratic <i>n</i> <sup>ε</sup> -approximation for the Continuous Fréchet Distance
日本大学: 関与なし（対象大学）
- A Tight Analysis of Slim Heaps and Smooth Heaps
日本大学: 関与なし（対象大学）
- A half-integral Erdős-Pósa theorem for directed odd cycles
日本大学: 関与なし（対象大学）
- A logic-based algorithmic meta-theorem for mim-width
日本大学: 関与なし（対象大学）
- A simple and sharper proof of the hypergraph Moore bound
日本大学: 関与なし（対象大学）
- A tight quasi-polynomial bound for Global Label Min-Cut
日本大学: 関与なし（対象大学）
- Algebraic Algorithms for Fractional Linear Matroid Parity via Non-commutative Rank
日本大学: 東京大学
- Algorithmizing the Multiplicity Schwartz-Zippel Lemma
日本大学: 関与なし（対象大学）
- Almost Consistent Systems of Linear Equations
日本大学: 関与なし（対象大学）
- Almost Tight Bounds for Online Facility Location in the Random-Order Model
日本大学: 関与なし（対象大学）
- Almost Tight Error Bounds on Differentially Private Continual Counting
日本大学: 関与なし（対象大学）
- Almost-Linear Planted Cliques Elude the Metropolis Process
日本大学: 関与なし（対象大学）
- An Improved Approximation for Maximum Weighted <i>k</i> -Set Packing
日本大学: 関与なし（対象大学）
- Approaching the Soundness Barrier: A Near Optimal Analysis of the Cube versus Cube Test
日本大学: 関与なし（対象大学）
- Approximate Distance Oracles for Planar Graphs with Subpolynomial Error Dependency
日本大学: 関与なし（対象大学）
- Approximate Graph Colouring and Crystals
日本大学: 関与なし（対象大学）
- Approximate Trace Reconstruction from a Single Trace
日本大学: 関与なし（対象大学）
- Approximating Knapsack and Partition via Dense Subset Sums
日本大学: 関与なし（対象大学）
- Approximation Algorithms for Steiner Tree Augmentation Problems
日本大学: 関与なし（対象大学）
- Balanced Allocations with Heterogeneous Bins: The Power of Memory
日本大学: 関与なし（対象大学）
- Beating (1 - 1/e)-Approximation for Weighted Stochastic Matching
日本大学: 関与なし（対象大学）
- Beating Greedy Matching in Sublinear Time
日本大学: 関与なし（対象大学）
- Bidder Subset Selection Problem in Auction Design
日本大学: 関与なし（対象大学）
- Breaching the 2 LMP Approximation Barrier for Facility Location with Applications to <i>k</i> -Median
日本大学: 関与なし（対象大学）
- Breaking the 𝒪( <i>n</i> )-Barrier in the Construction of Compressed Suffix Arrays and Suffix Trees
日本大学: 関与なし（対象大学）
- Byzantine Agreement with Optimal Resilience via Statistical Fraud Detection
日本大学: 関与なし（対象大学）
- Closing the Gap Between Directed Hopsets and Shortcut Sets
日本大学: 関与なし（対象大学）
- Competitive Information Design for Pandora's Box
日本大学: 関与なし（対象大学）
- Computing Square Colorings on Bounded-Treewidth and Planar Graphs
日本大学: 関与なし（対象大学）
- Concentration of polynomial random matrices via Efron-Stein inequalities
日本大学: 関与なし（対象大学）
- Conflict-free hypergraph matchings
日本大学: 関与なし（対象大学）
- Constant Approximating Parameterized <i>k</i> -SETCOVER is W[2]-hard
日本大学: 関与なし（対象大学）
- Cubic Goldreich-Levin
日本大学: 関与なし（対象大学）
- Curve Simplification and Clustering under Fréchet Distance
日本大学: 関与なし（対象大学）
- Deterministic counting Lovász local lemma beyond linear programming
日本大学: 関与なし（対象大学）
- Differentially Private All-Pairs Shortest Path Distances: Improved Algorithms and Lower Bounds
日本大学: 関与なし（対象大学）
- Discrepancy Minimization via Regularization
日本大学: 関与なし（対象大学）
- Distributed Maximal Matching and Maximal Independent Set on Hypergraphs
日本大学: 関与なし（対象大学）
- Dynamic Algorithms for Maximum Matching Size
日本大学: 関与なし（対象大学）
- Dynamic Algorithms for Packing-Covering LPs via Multiplicative Weight Updates
日本大学: 関与なし（対象大学）
- Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time
日本大学: 関与なし（対象大学）
- Economical Convex Coverings and Applications
日本大学: 関与なし（対象大学）
- Efficient decoding up to a constant fraction of the code length for asymptotically good quantum codes
日本大学: 関与なし（対象大学）
- Efficient resilient functions
日本大学: 関与なし（対象大学）
- Elliptic Curve Fast Fourier Transform (ECFFT) Part I: Low-degree Extension in Time <i>O(n</i> log <i>n</i> ) over all Finite Fields
日本大学: 関与なし（対象大学）
- Equivalence Test for Read-Once Arithmetic Formulas
日本大学: 関与なし（対象大学）
- Exact Flow Sparsification Requires Unbounded Size
日本大学: 関与なし（対象大学）
- Excluding Single-Crossing Matching Minors in Bipartite Graphs
日本大学: 関与なし（対象大学）
- Fair allocation of a multiset of indivisible items
日本大学: 関与なし（対象大学）
- Fast Discrepancy Minimization with Hereditary Guarantees
日本大学: 関与なし（対象大学）
- Fast Distributed Brooks' Theorem
日本大学: 関与なし（対象大学）
- Fast algorithms for solving the Hamilton Cycle problem with high probability
日本大学: 関与なし（対象大学）
- Faster Algorithm for Turn-based Stochastic Games with Bounded Treewidth
日本大学: 関与なし（対象大学）
- Faster Computation of 3-Edge-Connected Components in Digraphs
日本大学: 関与なし（対象大学）
- Faster Deterministic Worst-Case Fully Dynamic All-Pairs Shortest Paths via Decremental Hop-Restricted Shortest Paths
日本大学: 関与なし（対象大学）
- Faster and Unified Algorithms for Diameter Reducing Shortcuts and Minimum Chain Covers
日本大学: 関与なし（対象大学）
- Finding Triangles and Other Small Subgraphs in Geometric Intersection Graphs
日本大学: 関与なし（対象大学）
- Fixed-Parameter Tractability of Maximum Colored Path and Beyond
日本大学: 関与なし（対象大学）
- Fixed-parameter tractability of DIRECTED MULTICUT with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation
日本大学: 関与なし（対象大学）
- Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints
日本大学: 関与なし（対象大学）
- Foundations of Transaction Fee Mechanism Design
日本大学: 関与なし（対象大学）
- From Algorithms to Connectivity and Back: Finding a Giant Component in Random <i>k</i> -SAT
日本大学: 関与なし（対象大学）
- Fully Dynamic Exact Edge Connectivity in Sublinear Time
日本大学: 関与なし（対象大学）
- Gap-ETH-Tight Approximation Schemes for Red-Green-Blue Separation and Bicolored Noncrossing Euclidean Travelling Salesman Tours
日本大学: 関与なし（対象大学）
- Generalized Unrelated Machine Scheduling Problem
日本大学: 関与なし（対象大学）
- Graph Classes with Few Minimal Separators. I. Finite Forbidden Induced Subgraphs
日本大学: 関与なし（対象大学）
- Graph Classes with Few Minimal Separators. II. A Dichotomy
日本大学: 関与なし（対象大学）
- Halving by a Thousand Cuts or Punctures
日本大学: 関与なし（対象大学）
- Hierarchies of Minion Tests for PCSPs through Tensors
日本大学: 関与なし（対象大学）
- Higher degree sum-of-squares relaxations robust against oblivious outliers
日本大学: 関与なし（対象大学）
- Improved Approximation for Two-Edge-Connectivity
日本大学: 関与なし（対象大学）
- Improved Approximations for Unrelated Machine Scheduling
日本大学: 関与なし（対象大学）
- Improved Bi-point Rounding Algorithms and a Golden Barrier for <i>k</i> -Median
日本大学: 関与なし（対象大学）
- Improved Bounds for Sampling Solutions of Random CNF Formulas
日本大学: 関与なし（対象大学）
- Improved Distributed Algorithms for the Lovász Local Lemma and Edge Coloring
日本大学: 関与なし（対象大学）
- Improved Distributed Network Decomposition, Hitting Sets, and Spanners, via Derandomization
日本大学: 関与なし（対象大学）
- Improved Integrality Gap in Max-Min Allocation: or Topology at the North Pole
日本大学: 関与なし（対象大学）
- Improved Pattern-Avoidance Bounds for Greedy BSTs via Matrix Decomposition
日本大学: 関与なし（対象大学）
- Improved girth approximation in weighted undirected graphs
日本大学: 関与なし（対象大学）
- Instability of backoff protocols with arbitrary arrival rates
日本大学: 関与なし（対象大学）
- Integrality Gaps for Random Integer Programs via Discrepancy
日本大学: 関与なし（対象大学）
- Interactive Coding with Small Memory
日本大学: 関与なし（対象大学）
- Interdependent Public Projects
日本大学: 関与なし（対象大学）
- Kernelization for Graph Packing Problems via Rainbow Matching
日本大学: 関与なし（対象大学）
- Learning Hierarchical Cluster Structure of Graphs in Sublinear Time
日本大学: 関与なし（対象大学）
- Local Distributed Rounding: Generalized to MIS, Matching, Set Cover, and Beyond
日本大学: 関与なし（対象大学）
- Lossless Online Rounding for Online Bipartite Matching (Despite its Impossibility)
日本大学: 関与なし（対象大学）
- Low Degree Testing over the Reals
日本大学: 関与なし（対象大学）
- Maintaining Expander Decompositions via Sparse Cuts
日本大学: 関与なし（対象大学）