Conferences · eligible papers
SODA
2021–2025 確定版
2021 · 180 papers
このEditionに反映済みのmain full research papersのみ掲載しています。著者リンクは日本の大学への著者別所属根拠がある場合に限ります。
- (Near-)Linear-Time Randomized Algorithms for Row Minima in Monge Partial Matrices and Related Problems
日本大学: 関与なし（対象大学）
- 2-Level Quasi-Planarity or How Caterpillars Climb (SPQR-)Trees
日本大学: 関与なし（対象大学）
- A Constant Factor Approximation for Navigating Through Connected Obstacles in the Plane
日本大学: 関与なし（対象大学）
- A Deterministic Parallel APSP Algorithm and its Applications
日本大学: 関与なし（対象大学）
- A Fast Minimum Degree Algorithm and Matching Lower Bound
日本大学: 関与なし（対象大学）
- A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics
日本大学: 関与なし（対象大学）
- A Fine-Grained Perspective on Approximating Subset Sum and Partition
日本大学: 関与なし（対象大学）
- A Local Search Framework for Experimental Design
日本大学: 関与なし（対象大学）
- A Lower Bound for Dynamic Fractional Cascading
日本大学: 関与なし（対象大学）
- A Polynomial Time Algorithm for the <i>k</i> -Disjoint Shortest Paths Problem
日本大学: 関与なし（対象大学）
- A Refined Laser Method and Faster Matrix Multiplication
日本大学: 関与なし（対象大学）
- A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Privacy
日本大学: 関与なし（対象大学）
- A Time-Optimal Randomized Parallel Algorithm for MIS
日本大学: 関与なし（対象大学）
- A Topological Characterization of Modulo- <i>p</i> Arguments and Implications for Necklace Splitting
日本大学: 関与なし（対象大学）
- A tight condition for triangle factors in pseudorandom graphs
日本大学: 関与なし（対象大学）
- Algorithms for Persuasion with Limited Communication
日本大学: 関与なし（対象大学）
- Algorithms for weighted independent transversals and strong colouring
日本大学: 関与なし（対象大学）
- All-Pairs LCA in DAGs: Breaking through the <i>O</i> ( <i>n</i> <sup>2.5</sup> ) barrier
日本大学: 関与なし（対象大学）
- An <i>O</i> ( <i>n</i> <sup>5/4</sup> ) Time <i>∊</i> -Approximation Algorithm for RMS Matching in a Plane
日本大学: 関与なし（対象大学）
- An Efficient <i>∊</i> -BIC to BIC Transformation and Its Application to Black-Box Reduction in Revenue Maximization
日本大学: 関与なし（対象大学）
- An FPTAS for the square lattice six-vertex and eight-vertex models at low temperatures
日本大学: 関与なし（対象大学）
- An improved procedure for colouring graphs of bounded local density
日本大学: 関与なし（対象大学）
- Analytic quantum weak coin flipping protocols with arbitrarily small bias
日本大学: 関与なし（対象大学）
- Approximate Distance Oracles Subject to Multiple Vertex Failures
日本大学: 関与なし（対象大学）
- Approximate Evaluation of First-Order Counting Queries
日本大学: 関与なし（対象大学）
- Approximate Nearest Neighbors Beyond Space Partitions
日本大学: 関与なし（対象大学）
- Approximating ( <i>k, ℓ</i> -Median Clustering for Polygonal Curves
日本大学: 関与なし（対象大学）
- Approximating Pathwidth for Graphs of Small Treewidth
日本大学: 関与なし（対象大学）
- Approximating Permanent of Random Matrices with Vanishing Mean: Made Better and Simpler
日本大学: 関与なし（対象大学）
- Approximating the Median under the Ulam Metric
日本大学: 関与なし（対象大学）
- Approximation Algorithms and Hardness for Strong Unique Games
日本大学: 関与なし（対象大学）
- Asymptotic dimension of minor-closed families and beyond
日本大学: 関与なし（対象大学）
- Atomic Power in Forks: A Super-Logarithmic Lower Bound for Implementing Butterfly Networks in the Nonatomic Binary Fork-Join Model
日本大学: 関与なし（対象大学）
- Average Sensitivity of Graph Algorithms
日本大学: 関与なし（対象大学）
- Beating Greedy For Approximating Reserve Prices in Multi-Unit VCG Auctions
日本大学: 関与なし（対象大学）
- Beating the probabilistic lower bound on perfect hashing
日本大学: 関与なし（対象大学）
- Being Fast Means Being Chatty: The Local Information Cost of Graph Spanners
日本大学: 関与なし（対象大学）
- Beyond Submodular Maximization via One-Sided Smoothness
日本大学: 関与なし（対象大学）
- Block-Structured Integer and Linear Programming in Strongly Polynomial and Near Linear Time
日本大学: 関与なし（対象大学）
- Branch-and-Bound Solves Random Binary IPs in Polytime
日本大学: 関与なし（対象大学）
- Coloring and Maximum Weight Independent Set of Rectangles
日本大学: 関与なし（対象大学）
- Competitive Allocation of a Mixed Manna
日本大学: 関与なし（対象大学）
- Competitive Data-Structure Dynamization
日本大学: 関与なし（対象大学）
- Concentration bounds for almost <i>k</i> -wise independence with applications to non-uniform security
日本大学: 関与なし（対象大学）
- Connecting Robust Shuffle Privacy and Pan-Privacy
日本大学: 関与なし（対象大学）
- Consistent k-Clustering for General Metrics
日本大学: 関与なし（対象大学）
- Constrained-Order Prophet Inequalities
日本大学: 関与なし（対象大学）
- Coresets for Clustering in Excluded-minor Graphs and Beyond
日本大学: 関与なし（対象大学）
- Counting Homomorphisms to <i>K</i> <sub>4</sub> -minor-free Graphs, modulo 2
日本大学: 関与なし（対象大学）
- Counting Small Permutation Patterns
日本大学: 関与なし（対象大学）
- Decomposing the Complement of the Union of Cubes in Three Dimensions
日本大学: 関与なし（対象大学）
- Deep Weisfeiler Leman
日本大学: 関与なし（対象大学）
- Deterministic Algorithms for Decremental Shortest Paths via Layered Core Decomposition
日本大学: 関与なし（対象大学）
- Deterministic Replacement Path Covering
日本大学: 関与なし（対象大学）
- Dimension-Preserving Reductions Between SVP and CVP in Different <i>p</i> -Norms
日本大学: 関与なし（対象大学）
- Directed Shortest Paths via Approximate Cost Balancing
日本大学: 関与なし（対象大学）
- Distributed Metropolis Sampler with Optimal Parallelism
日本大学: 関与なし（対象大学）
- Dynamic Graph Algorithms with Batch Updates in the Massively Parallel Computation Model
日本大学: 関与なし（対象大学）
- Dynamic Maintenance of Low-Stretch Probabilistic Tree Embeddings with Applications
日本大学: 関与なし（対象大学）
- Dynamic Set Cover: Improved Amortized and Worst-Case Update Time
日本大学: 関与なし（対象大学）
- EPTAS for <i>k</i> -means Clustering of Affine Subspaces
日本大学: 関与なし（対象大学）
- Efficient Computation of Representative Weight Functions with Applications to Parameterized Counting (Extended Version)
日本大学: 関与なし（対象大学）
- Efficient Document Exchange and Error Correcting Codes with Asymmetric Information
日本大学: 関与なし（対象大学）
- Efficient Linear and Affine Codes for Correcting Insertions/Deletions
日本大学: 関与なし（対象大学）
- Efficient fully dynamic elimination forests with applications to detecting long paths and cycles
日本大学: 関与なし（対象大学）
- Estimating the Nash Social Welfare for coverage and other submodular valuations
日本大学: 関与なし（対象大学）
- Explicit two-deletion codes with redundancy matching the existential bound
日本大学: 関与なし（対象大学）
- FPT-approximation for FPT Problems
日本大学: 関与なし（対象大学）
- Fast Convergence of Fictitious Play for Diagonal Payoff Matrices
日本大学: 関与なし（対象大学）
- Fast Low-Space Algorithms for Subset Sum
日本大学: 関与なし（対象大学）
- Fine-grained hardness of CVP(P)—Everything that we can prove (and nothing else)
日本大学: 関与なし（対象大学）
- Graph Spanners by Sketching in Dynamic Streams and the Simultaneous Communication Model
日本大学: 関与なし（対象大学）
- Hamiltonicity of random subgraphs of the hypercube
日本大学: 関与なし（対象大学）
- Hardness of Approximation for Orienteering with Multiple Time Windows
日本大学: 関与なし（対象大学）
- How Many Vertices Does a Random Walk Miss in a Network with Moderately Increasing the Number of Vertices?
- How to Morph Graphs on the Torus
日本大学: 関与なし（対象大学）
- Improved Algorithms for Population Recovery from the Deletion Channel
日本大学: 関与なし（対象大学）
- Improved Algorithms for Solving Polynomial Systems over GF(2) by Multiple Parity-Counting
日本大学: 関与なし（対象大学）
- Improved Approximations for Min Sum Vertex Cover and Generalized Min Sum Set Cover
日本大学: 関与なし（対象大学）
- Improved Deterministic Network Decomposition
日本大学: 関与なし（対象大学）
- Improved Sublinear Time Algorithm for Longest Increasing Subsequence
日本大学: 関与なし（対象大学）
- Improved Truthful Mechanisms for Subadditive Combinatorial Auctions: Breaking the Logarithmic Barrier
日本大学: 関与なし（対象大学）
- Improving the dilation of a metric graph by adding edges
日本大学: 関与なし（対象大学）
- In which matching markets does the short side enjoy an advantage?
日本大学: 関与なし（対象大学）
- Incremental Single Source Shortest Paths in Sparse Digraphs
日本大学: 関与なし（対象大学）
- Induced subgraphs of bounded treewidth and the container method
日本大学: 関与なし（対象大学）
- Infinite-Duration All-Pay Bidding Games
日本大学: 関与なし（対象大学）
- Lee-Yang zeros and the complexity of the ferromagnetic Ising Model on bounded-degree graphs
日本大学: 関与なし（対象大学）
- List-Decodable Subspace Recovery: Dimension Independent Error in Polynomial Time
日本大学: 関与なし（対象大学）
- Local Statistics, Semidefinite Programming, and Community Detection
日本大学: 関与なし（対象大学）
- Min-max Partitioning of Hypergraphs and Symmetric Submodular Functions
日本大学: 関与なし（対象大学）
- Minimizing Convex Functions with Integral Minimizers
日本大学: 関与なし（対象大学）
- Minimum-cost integer circulations in given homology classes
日本大学: 関与なし（対象大学）
- Near-Linear Time Homomorphism Counting in Bounded Degeneracy Graphs: The Barrier of Long Induced Cycles
日本大学: 関与なし（対象大学）
- Near-Optimal Randomized Algorithms for Selection in Totally Monotone Matrices
日本大学: 関与なし（対象大学）
- Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH
日本大学: 東京大学
- New Data Structures for Orthogonal Range Reporting and Range Minima Queries
日本大学: 関与なし（対象大学）
- New Planar P-time Computable Six-Vertex Models and a Complete Complexity Classification
日本大学: 関与なし（対象大学）
- New Techniques and Fine-Grained Hardness for Dynamic Near-Additive Spanners
日本大学: 関与なし（対象大学）
- Non-Excludable Dynamic Mechanism Design
日本大学: 関与なし（対象大学）