Conferences · eligible papers
SODA
2022–2026 LIVE
2023 · 190 papers
このEditionに反映済みのmain full research papersのみ掲載しています。著者リンクは日本の大学への著者別所属根拠がある場合に限ります。
- Map matching queries on realistic input graphs under the Fréchet distance
日本大学: 関与なし（対象大学）
- Massively Parallel Computation on Embedded Planar Graphs
日本大学: 関与なし（対象大学）
- Maximal <i>k</i> -Edge-Connected Subgraphs in Weighted Graphs via Local Random Contraction
日本大学: 関与なし（対象大学）
- Mean estimation when you have the source code; or, quantum Monte Carlo methods
日本大学: 関与なし（対象大学）
- Minimizing Completion Times for Stochastic Jobs via Batched Free Times
日本大学: 関与なし（対象大学）
- Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes
日本大学: 関与なし（対象大学）
- Moser-Tardos Algorithm: Beyond Shearer's Bound
日本大学: 関与なし（対象大学）
- Near-Linear Sample Complexity for <i> L <sub>p</sub> </i> Polynomial Regression
日本大学: 関与なし（対象大学）
- Near-Linear Time Approximations for Cut Problems via Fair Cuts
日本大学: 関与なし（対象大学）
- Non-Stochastic CDF Estimation Using Threshold Queries
日本大学: 関与なし（対象大学）
- Nonlinear codes exceeding the Gilbert-Varshamov and Tsfasman-Vlăduţ-Zink bounds
日本大学: 関与なし（対象大学）
- On (Random-order) Online Contention Resolution Schemes for the Matching Polytope of (Bipartite) Graphs
日本大学: 関与なし（対象大学）
- On Minimizing Tardy Processing Time, Max-Min Skewed Convolution, and Triangular Structured ILPs
日本大学: 関与なし（対象大学）
- On Problems Related to Unbounded SubsetSum: A Unified Combinatorial Approach
日本大学: 関与なし（対象大学）
- On complex roots of the independence polynomial
日本大学: 関与なし（対象大学）
- On the Integrality Gap of MFN Relaxation for the Capacitated Facility Location Problem
日本大学: 関与なし（対象大学）
- On the Number of Incidences When Avoiding an Induced Biclique in Geometric Settings
日本大学: 関与なし（対象大学）
- On the orbit closure intersection problems for matrix tuples under conjugation and left-right actions
日本大学: 関与なし（対象大学）
- Online Lewis Weight Sampling
日本大学: 関与なし（対象大学）
- Online Min-Max Paging
日本大学: 関与なし（対象大学）
- Online Prediction in Sub-linear Space
日本大学: 関与なし（対象大学）
- Online Sorting and Translational Packing of Convex Polygons
日本大学: 関与なし（対象大学）
- Online and Bandit Algorithms Beyond ℓ <sub> <i>p</i> </sub> Norms
日本大学: 関与なし（対象大学）
- Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time
日本大学: 関与なし（対象大学）
- Optimal Deterministic Massively Parallel Connectivity on Forests
日本大学: 関与なし（対象大学）
- Optimal Fully Dynamic <i>k</i> -Center Clustering for Adaptive and Oblivious Adversaries
日本大学: 関与なし（対象大学）
- Optimal Pricing Schemes for an Impatient Buyer
日本大学: 関与なし（対象大学）
- Optimal Square Detection Over General Alphabets
日本大学: 関与なし（対象大学）
- Packing cycles in planar and bounded-genus graphs
日本大学: 関与なし（対象大学）
- Parallel Exact Shortest Paths in Almost Linear Work and Square Root Depth
日本大学: 関与なし（対象大学）
- Parameterized Algorithm for the Disjoint Path Problem on Planar Graphs: Exponential in <i>k</i> <sup>2</sup> and Linear in <i>n</i>
日本大学: 関与なし（対象大学）
- Parameterized Approximation Scheme for Biclique-free Max <i>k</i> -Weight SAT and Max Coverage
日本大学: 関与なし（対象大学）
- Passing the Limits of Pure Local Search for Weighted <i>k</i> -Set Packing
日本大学: 関与なし（対象大学）
- Player-optimal Stable Regret for Bandit Learning in Matching Markets
日本大学: 関与なし（対象大学）
- Polynomial formulations as a barrier for reduction-based hardness proofs
日本大学: 関与なし（対象大学）
- Positivity of the symmetric group characters is as hard as the polynomial time hierarchy
日本大学: 関与なし（対象大学）
- Pricing Query Complexity of Revenue Maximization
日本大学: 関与なし（対象大学）
- Private Convex Optimization in General Norms
日本大学: 関与なし（対象大学）
- Private Query Release via the Johnson-Lindenstrauss Transform
日本大学: 関与なし（対象大学）
- Quantum Speed-ups for String Synchronizing Sets, Longest Common Substring, and <i>k</i> -mismatch Matching
日本大学: 関与なし（対象大学）
- Quantum tomography using state-preparation unitaries
日本大学: 関与なし（対象大学）
- Query Complexity of Inversion Minimization on Trees
日本大学: 関与なし（対象大学）
- Query Complexity of the Metric Steiner Tree Problem
日本大学: 関与なし（対象大学）
- Robust Voting Rules from Algorithmic Robust Statistics
日本大学: 関与なし（対象大学）
- Sampling Equilibria: Fast No-Regret Learning in Structured Games
日本大学: 関与なし（対象大学）
- Secretary Problems: The Power of a Single Sample
日本大学: 関与なし（対象大学）
- Sharp threshold sequence and universality for Ising perceptron models
日本大学: 明治大学
- Short Synchronizing Words for Random Automata
日本大学: 関与なし（対象大学）
- Shortest Cycles With Monotone Submodular Costs
日本大学: 関与なし（対象大学）
- Shrunk subspaces via operator Sinkhorn iteration
日本大学: 関与なし（対象大学）
- Simple Mechanisms for Non-linear Agents
日本大学: 関与なし（対象大学）
- Simple, deterministic, fast (but weak) approximations to edit distance and Dyck edit distance
日本大学: 関与なし（対象大学）
- Simplex Range Searching Revisited: How to Shave Logs in Multi-Level Data Structures
日本大学: 関与なし（対象大学）
- Single-Pass Streaming Algorithms for Correlation Clustering
日本大学: 関与なし（対象大学）
- Small Shadows of Lattice Polytopes
日本大学: 関与なし（対象大学）
- Small subgraphs with large average degree
日本大学: 関与なし（対象大学）
- Smaller Low-Depth Circuits for Kronecker Powers
日本大学: 関与なし（対象大学）
- Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
日本大学: 関与なし（対象大学）
- Spatial mixing and the random-cluster dynamics on lattices
日本大学: 関与なし（対象大学）
- Spencer's theorem in nearly input-sparsity time
日本大学: 関与なし（対象大学）
- Steiner Connectivity Augmentation and Splitting-off in Poly-logarithmic Maximum Flows
日本大学: 関与なし（対象大学）
- Streaming algorithms for the missing item finding problem
日本大学: 関与なし（対象大学）
- Streaming complexity of CSPs with randomly ordered constraints
日本大学: 関与なし（対象大学）
- Stronger 3SUM-Indexing Lower Bounds
日本大学: 関与なし（対象大学）
- Stronger Privacy Amplification by Shuffling for Renyi and Approximate Differential Privacy
日本大学: 関与なし（対象大学）
- Subexponential mixing for partition chains on grid-like graphs
日本大学: 関与なし（対象大学）
- Sublinear-Time Algorithms for Max Cut, Max E2Lin( <i>q</i> ), and Unique Label Cover on Expanders
日本大学: 関与なし（対象大学）
- Super-resolution and Robust Sparse Continuous Fourier Transform in Any Constant Dimension: Nearly Linear Time and Sample Complexity
日本大学: 関与なし（対象大学）
- Superpolynomial lower bounds for decision tree learning and testing
日本大学: 関与なし（対象大学）
- Testing Convex Truncation
日本大学: 関与なし（対象大学）
- Testing and Learning Quantum Juntas Nearly Optimally
日本大学: 関与なし（対象大学）
- The Exact Bipartite Matching Polytope Has Exponential Extension Complexity
日本大学: 関与なし（対象大学）
- The Need for Seed (in the abstract Tile Assembly Model)
日本大学: 関与なし（対象大学）
- The Power of Clairvoyance for Multi-Level Aggregation and Set Cover with Delay
日本大学: 関与なし（対象大学）
- The Price of Stability for First Price Auction
日本大学: 関与なし（対象大学）
- The complete classification for quantified equality constraints
日本大学: 関与なし（対象大学）
- The ℓ <sub> <i>p</i> </sub> -Subspace Sketch Problem in Small Dimensions with Applications to Support Vector Machines
日本大学: 関与なし（対象大学）
- Tight Bounds for Monotone Minimal Perfect Hashing
日本大学: 関与なし（対象大学）
- Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs
日本大学: 関与なし（対象大学）
- Time-Space Tradeoffs for Element Distinctness and Set Intersection via Pseudorandomness
日本大学: 関与なし（対象大学）
- Timeliness Through Telephones: Approximating Information Freshness in Vector Clock Models
日本大学: 関与なし（対象大学）
- Tiny Pointers
日本大学: 関与なし（対象大学）
- Toeplitz Low-Rank Approximation with Sublinear Query Complexity
日本大学: 関与なし（対象大学）
- Towards Multi-Pass Streaming Lower Bounds for Optimal Approximation of Max-Cut
日本大学: 関与なし（対象大学）
- Traversing the FFT Computation Tree for Dimension-Independent Sparse Fourier Transforms
日本大学: 関与なし（対象大学）
- Unique Games hardness of Quantum Max-Cut, and a conjectured vector-valued Borell's inequality
日本大学: 関与なし（対象大学）
- Weak Bisimulation Finiteness of Pushdown Systems With Deterministic ε-Transitions Is 2-EXPTIME-Complete
日本大学: 関与なし（対象大学）
- Weisfeiler-Leman and Graph Spectra
日本大学: 関与なし（対象大学）
- Zigzagging through acyclic orientations of chordal graphs and hypergraphs
日本大学: 関与なし（対象大学）
- “Who is Next in Line?” On the Significance of Knowing the Arrival Order in Bayesian Online Settings
日本大学: 関与なし（対象大学）