Conferences · eligible papers
SODA
2021–2025 確定版
2022 · 148 papers
このEditionに反映済みのmain full research papersのみ掲載しています。著者リンクは日本の大学への著者別所属根拠がある場合に限ります。
- A 3-Approximation Algorithm for Maximum Independent Set of Rectangles
日本大学: 関与なし（対象大学）
- A Deterministic Parallel Reduction from Weighted Matroid Intersection Search to Decision
日本大学: 関与なし（対象大学）
- A Faster Algorithm for Quickest Transshipments via an Extended Discrete Newton Method
日本大学: 関与なし（対象大学）
- A Framework for Parameterized Subexponential Algorithms for Generalized Cycle Hitting Problems on Planar Graphs
日本大学: 関与なし（対象大学）
- A Lower Bound for the <i>n</i> -queens Problem
日本大学: 関与なし（対象大学）
- A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs
日本大学: 関与なし（対象大学）
- A Sublinear Bound on the Page Number of Upward Planar Graphs
日本大学: 関与なし（対象大学）
- A Tail Estimate with Exponential Decay for the Randomized Incremental Construction of Search Structures
日本大学: 関与なし（対象大学）
- A Two-Pass (Conditional) Lower Bound for Semi-Streaming Maximum Matching
日本大学: 関与なし（対象大学）
- Algorithmic Extensions of Dirac's Theorem
日本大学: 関与なし（対象大学）
- Algorithmic Thresholds for Refuting Random Polynomial Systems
日本大学: 関与なし（対象大学）
- Algorithmic trade-offs for girth approximation in undirected graphs
日本大学: 関与なし（対象大学）
- Algorithms Using Local Graph Features to Predict Epidemics
日本大学: 関与なし（対象大学）
- Almost Tight Approximation Algorithms for Explainable Clustering
日本大学: 関与なし（対象大学）
- An Improved Algorithm for The <i>k</i> -Dyck Edit Distance Problem
日本大学: 関与なし（対象大学）
- An Improved Analysis of Greedy for Online Steiner Forest
日本大学: 関与なし（対象大学）
- An Improved Local Search Algorithm for <i>k</i> -Median
日本大学: 関与なし（対象大学）
- An Upper Bound and Linear-Space Queries on the LZ-End Parsing
日本大学: 関与なし（対象大学）
- Approximate Core for Committee Selection via Multilinear Extension and Market Clearing
日本大学: 関与なし（対象大学）
- Approximate Hypergraph Vertex Cover and generalized Tuza's conjecture
日本大学: 関与なし（対象大学）
- Approximately counting independent sets in bipartite graphs via graph containers
日本大学: 関与なし（対象大学）
- Approximating Equilibrium under Constrained Piecewise Linear Concave Utilities with Applications to Matching Markets
日本大学: 関与なし（対象大学）
- Approximating Fair Clustering with Cascaded Norm Objectives
日本大学: 関与なし（対象大学）
- Approximating Sumset Size
日本大学: 関与なし（対象大学）
- Approximating the Arboricity in Sublinear Time
日本大学: 関与なし（対象大学）
- Approximation Schemes for Capacitated Vehicle Routing on Graphs of Bounded Treewidth, Bounded Doubling, or Highway Dimension
日本大学: 関与なし（対象大学）
- Augmenting Edge Connectivity via Isolating Cuts
日本大学: 関与なし（対象大学）
- Average Sensitivity of Dynamic Programming
日本大学: 東京大学
- Average-Case Subset Balancing Problems
日本大学: 関与なし（対象大学）
- Balanced Allocations: Caching and Packing, Twinning and Thinning
日本大学: 関与なし（対象大学）
- Better Lower Bounds for Shortcut Sets and Additive Spanners via an Improved Alternation Product
日本大学: 関与なし（対象大学）
- Better Sum Estimation via Weighted Sampling
日本大学: 関与なし（対象大学）
- CLAP: A New Algorithm for Promise CSPs
日本大学: 関与なし（対象大学）
- Co-evolution of Opinion and Social Tie Dynamics Towards Structural Balance
日本大学: 関与なし（対象大学）
- Collapsing the Tower - On the Complexity of Multistage Stochastic IPs
日本大学: 関与なし（対象大学）
- Combinatorial Gap Theorem and Reductions between Promise CSPs
日本大学: 関与なし（対象大学）
- Compact Redistricting Plans Have Many Spanning Trees
日本大学: 関与なし（対象大学）
- Competitive Strategies for Symmetric Rendezvous on the Line
日本大学: 関与なし（対象大学）
- Computational Hardness of the Hylland-Zeckhauser Scheme
日本大学: 関与なし（対象大学）
- Computational Topology in a Collapsing Universe: Laplacians, Homology, Cohomology
日本大学: 関与なし（対象大学）
- Computing Lewis Weights to High Precision
日本大学: 関与なし（対象大学）
- Congruency-Constrained TU Problems Beyond the Bimodular Case
日本大学: 関与なし（対象大学）
- Constructing Many Faces in Arrangements of Lines and Segments
日本大学: 関与なし（対象大学）
- Counting Homomorphic Cycles in Degenerate Graphs
日本大学: 関与なし（対象大学）
- Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds
日本大学: 関与なし（対象大学）
- Cubic upper and lower bounds for subtrajectory clustering under the continuous Fréchet distance
日本大学: 関与なし（対象大学）
- Cut Sparsification of the Clique Beyond the Ramanujan Bound: A Separation of Cut Versus Spectral Sparsification
日本大学: 関与なし（対象大学）
- Deleting, Eliminating and Decomposing to Hereditary Classes Are All FPT-Equivalent
日本大学: 関与なし（対象大学）
- Densest Subgraph: Supermodularity, Iterative Peeling, and Flow
日本大学: 関与なし（対象大学）
- Deterministic Budget-Feasible Clock Auctions
日本大学: 関与なし（対象大学）
- Deterministic algorithms for the Lovász Local Lemma: simpler, more general, and more parallel
日本大学: 関与なし（対象大学）
- Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution
日本大学: 関与なし（対象大学）
- Deterministic enumeration of all minimum <i>k</i> -cut-sets in hypergraphs for fixed <i>k</i>
日本大学: 関与なし（対象大学）
- Directed Tangle Tree-Decompositions and Applications
日本大学: 関与なし（対象大学）
- Distortion-Oblivious Algorithms for Minimizing Flow Time
日本大学: 関与なし（対象大学）
- Distributed Zero-Knowledge Proofs Over Networks
日本大学: 関与なし（対象大学）
- Distribution-free Testing for Halfspaces (Almost) Requires PAC Learning
日本大学: 関与なし（対象大学）
- Dynamic Geometric Set Cover, Revisited
日本大学: 関与なし（対象大学）
- Efficient generation of elimination trees and graph associahedra
日本大学: 関与なし（対象大学）
- Enumerating <i>k-SAT</i> functions
日本大学: 関与なし（対象大学）
- Fast Consensus via the Unconstrained Undecided State Dynamics
日本大学: 関与なし（対象大学）
- Faster Algorithms for Bounded-Difference Min-Plus Product
日本大学: 関与なし（対象大学）
- Fixed-Price Approximations in Bilateral Trade
日本大学: 関与なし（対象大学）
- Frequency Estimation with One-Sided Error
日本大学: 関与なし（対象大学）
- Friendly Cut Sparsifiers and Faster Gomory-Hu Trees
日本大学: 関与なし（対象大学）
- Greedy Spanners in Euclidean Spaces Admit Sublinear Separators
日本大学: 関与なし（対象大学）
- High Dimensional Expanders: Eigenstripping, Pseudorandomness, and Unique Games
日本大学: 関与なし（対象大学）
- Hopcroft's Problem, Log-Star Shaving, 2D Fractional Cascading, and Decision Trees
日本大学: 関与なし（対象大学）
- How Compression and Approximation Affect Efficiency in String Distance Measures
日本大学: 関与なし（対象大学）
- How many Clusters? - An algorithmic answer
日本大学: 関与なし（対象大学）
- Improved Algorithms for Low Rank Approximation from Sparsity
日本大学: 関与なし（対象大学）
- Improved Sliding Window Algorithms for Clustering and Coverage via Bucketing-Based Sketches
日本大学: 関与なし（対象大学）
- Improved Strongly Polynomial Algorithms for Deterministic MDPs, 2VPI Feasibility, and Discounted All-Pairs Shortest Paths
日本大学: 関与なし（対象大学）
- Incremental SSSP for Sparse Digraphs Beyond the Hopset Barrier
日本大学: 関与なし（対象大学）
- Isomorphism Testing for Graphs Excluding Small Topological Subgraphs
日本大学: 関与なし（対象大学）
- Johnson Coverage Hypothesis: Inapproximability of <i>k</i> -means and <i>k</i> -median in <i> ℓ <sub>p</sub> </i> -metrics
日本大学: 関与なし（対象大学）
- Learning-Augmented Weighted Paging
日本大学: 関与なし（対象大学）
- Limits of Preprocessing for Single-Server PIR
日本大学: 関与なし（対象大学）
- Local Search for Weighted Tree Augmentation and Steiner Tree
日本大学: 関与なし（対象大学）
- Massively Parallel and Dynamic Algorithms for Minimum Size Clustering
日本大学: 関与なし（対象大学）
- Metric Distortion Bounds for Randomized Social Choice
日本大学: 関与なし（対象大学）
- Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams
- Multi-token Markov Game with Switching Costs
日本大学: 関与なし（対象大学）
- Near-Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time
日本大学: 関与なし（対象大学）
- Near-Optimal Average-Case Approximate Trace Reconstruction from Few Traces
日本大学: 関与なし（対象大学）
- Near-Optimal Explainable <i>k</i> -Means for All Dimensions
日本大学: 関与なし（対象大学）
- Near-Optimal Quantum Algorithms for String Problems
日本大学: 関与なし（対象大学）
- Near-Optimal Spanners for General Graphs in (Nearly) Linear Time
日本大学: 関与なし（対象大学）
- Nearly 2-Approximate Distance Oracles in Subquadratic Time
日本大学: 関与なし（対象大学）
- Nested Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear Time
日本大学: 関与なし（対象大学）
- New Diameter-Reducing Shortcuts and Directed Hopsets: Breaking the Barrier
日本大学: 関与なし（対象大学）
- New Trade-Offs for Fully Dynamic Matching via Hierarchical EDCS
日本大学: 関与なし（対象大学）
- On Mixing of Markov Chains: Coupling, Spectral Independence, and Entropy Factorization
日本大学: 関与なし（対象大学）
- On complete classes of valuated matroids
日本大学: 関与なし（対象大学）
- On finding exact solutions of linear programs in the oracle model
日本大学: 関与なし（対象大学）
- On the Fine-Grained Complexity of the Unbounded SubsetSum and the Frobenius Problem
日本大学: 関与なし（対象大学）
- On the Hardness of Scheduling With Non-Uniform Communication Delays
日本大学: 関与なし（対象大学）
- On the complexity of binary polynomial optimization over acyclic hypergraphs
日本大学: 関与なし（対象大学）
- Online Discrepancy with Recourse for Vectors and Graphs
日本大学: 関与なし（対象大学）
- Online Graph Algorithms with Predictions
日本大学: 関与なし（対象大学）