yusuke1997/dblp-id-title huggingface dataset:
Half integral packing, Erdős-Posá-property and graph minors
Approximate shortest paths in anisotropic regions
Deterministic Byzantine Agreement with Adaptive O ( n · f ) Communication
Online Combinatorial Auctions
Harmonic broadcasting is optimal
Bypassing UGC from some optimal geometric inapproximability results
Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP: extended abstract
On complex roots of the independence polynomial
Compacting cuts: a new linear formulation for minimum cut
Online Degree-Bounded Steiner Network Design
The Robot Localization Problem in Two Dimensions
Efficient solutions to relaxations of combinatorial problems with submodular penalties via the Lovász extension and non-smooth convex optimization
Improved Bounds for the Flat Wall Theorem
Derandomized concentration bounds for polynomials, and hypergraph maximal independent set
Sparsifying, Shrinking and Splicing for Minimum Path Cover in Parameterized Linear Time
Multicommodity Facility Location under Group Steiner Access Cost
Faster Random Generation of Linear Extensions
Generalized Perron-Frobenius Theorem for Multiple Choice Matrices, and Applications
A new characterization of maximal repetitions by Lyndon trees
SETH-Based Lower Bounds for Subset Sum and Bicriteria Path
Average Case Analysis of Dynamic Geometric Optimization
Power of Posted-price Mechanisms for Prophet Inequalities
A quasi-PTAS for the Two-Dimensional Geometric Knapsack Problem
Strongly refuting all semi-random Boolean CSPs
Fast dimension reduction using Rademacher series on dual BCH codes
Noisy sorting without resampling
Faster deterministic dictionaries
Private Query Release via the Johnson-Lindenstrauss Transform
How Far Can You Reach?
An algebraic algorithm for weighted linear matroid intersection
Computations with polynomial evaluation oracle: ruling out superlinear SETH-based lower bounds
On-line algorithms for the dynamic traveling repair problem
Smaller Low-Depth Circuits for Kronecker Powers
Online learning in online auctions
Experiments on Traveling Salesman Heuristics
Convergence of multivariate belief propagation, with applications to cuckoo hashing and load balancing
Matrix rounding with low error in small submatrices
Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization
Computing the Independence Polynomial: from the Tree Threshold down to the Roots
Tight Guarantees for Multi-unit Prophet Inequalities and Online Stochastic Knapsack
A Scaling Technique for Better Network Design
On Graph Crossing Number and Edge Planarization
A tight upper bound on the probabilistic embedding of series-parallel graphs
Tight Revenue Gaps among Simple Mechanisms
Simultaneous optimization for concave costs: single sink aggregation or single source buy-at-bulk
An O(n log n log log n) Algorithm for the On-Line Closest Pair Problem
Improving the smoothed complexity of FLIP for max cut problems
On-Line File Caching
Two-Dimensional Gantt Charts and a Scheduling Algorithm of Lawler
A Treehouse with Custom Windows: Minimum Distortion Embeddings into Bounded Treewidth Graphs
Fully Dynamic Algorithms for Graph Spanners via Low-Diameter Router Decomposition
A Representation for Crossing Set Families with Applications to Submodular Flow Problems
More Compact Oracles for Approximate Distances in Undirected Planar Graphs
On Efficient Unsuccessful Search
An optimal online algorithm for packet scheduling with agreeable deadlines
Efficient Sequential and Parallel Algorithms for Computing Recovery Points in Trees and Paths
Simple Greedy 2-Approximation Algorithm for the Maximum Genus of a Graph
Factors and loose Hamilton cycles in sparse pseudo-random hypergraphs
Sorting and Selection in Rounds with Adversarial Comparisons
On-line Choice of On-line Algorithms
Rectangular Tiling in Multi-dimensional Arrays
Local-Search based Approximation Algorithms for Mobile Facility Location Problems
On the Parallel Complexity of Evaluating Game Trees
A locality-preserving cache-oblivious dynamic dictionary
A new approach to incremental topological ordering
Atomic Power in Forks: A Super-Logarithmic Lower Bound for Implementing Butterfly Networks in the Nonatomic Binary Fork-Join Model
Improved Approximation for Two-Edge-Connectivity
Nearly Optimal Average-Case Complexity of Counting Bicliques Under SETH
Curve Simplification and Clustering under Fréchet Distance
Self-improving Algorithms for Convex Hulls
Online Duet between Metric Embeddings and Minimum-Weight Perfect Matchings
On Brambles, Grid-Like Minors, and Parameterized Intractability of Monadic Second-Order Logic
Finding small patterns in permutations in linear time
Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time
An Improved Algorithm for The k-Dyck Edit Distance Problem
LSH-preserving functions and their applications
Fully persistent B-trees
Efficient algorithms for computing the triplet and quartet distance between trees of arbitrary degree
On the Parallel Time Complexity of Undirected Connectivity and Minimum Spanning Trees
Facility location with Service Installation Costs
Spatial Mixing and Non-local Markov chains
On Multi-Dimensional Gains from Trade Maximization
Efficiently Decodable Non-adaptive Group Testing
The rank of sparse random matrices
Approximate classification via earthmover metrics
Fast Sampling of b -Matchings and b -Edge Covers
An FPTAS for Counting Proper Four-Colorings on Cubic Graphs
Optimal detection of intersections between convex polyhedra
Linear Size Sparsifier and the Geometry of the Operator Norm Ball
Probability, algorithms and complexity
The Sparse Parity Matrix
Bidimensionality and geometric graphs
Cross-Referenced Dictionaries and the Limits of Write Optimization
Combinatorial Approach for Factorization of Variance and Entropy in Spin Systems
Beyond Highway Dimension: Small Distance Labels Using Tree Skeletons
Greedy Algorithms for Optimized DNA Sequencing
FPT-approximation for FPT Problems
Query Complexity of Inversion Minimization on Trees
Correlation clustering with a fixed number of clusters
An Efficient Protocol for Unconditionally Secure Secret Key Exchange
How to Store a Random Walk
Sorting from Noisier Samples
Nearly Optimal Black Box Polynomial Root-finders
Recognizing Sumsets is NP-Complete
Minimizing weighted flow time
Coarse-Grained Complexity for Dynamic Algorithms
Tiling a Figure Using a Height in a Tree
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011
Locally satisfiable formulas
On smoothed k -CNF formulas and the Walksat algorithm
Round Complexity of Common Randomness Generation: The Amortized Setting
Applications of the Fusion Tree Method to Computational Geometry and Searching
Single-Sample Prophet Inequalities via Greedy-Ordered Selection
Tightening Curves on Surfaces via Local Moves
Relaxed Locally Correctable Codes with Nearly-Linear Block Length and Constant Query Complexity
Balanced allocation on graphs
Learning Sparse Polynomial Functions
Improved Approximation Algorithms for Network Design Problems
Counting and Finding Homomorphisms is Universal for Parameterized Complexity Theory
A Polynomial Excluded-Minor Approximation of Treedepth
Belief Propagation for Min-cost Network Flow: Convergence & Correctness
Simpler and Higher Lower Bounds for Shortcut Sets
A point-placement strategy for conforming Delaunay tetrahedralization
Smoothed Complexity of SWAP in Local Graph Partitioning
Simultaneous PQ-Ordering with Applications to Constrained Embedding Problems
Scalably scheduling processes with arbitrary speedup curves
Biased range trees
Sub-Exponential Lower Bounds for Branch-and-Bound with General Disjunctions via Interpolation
Arc-disjoint in-trees in directed graphs
Better Lower Bounds for Shortcut Sets and Additive Spanners via an Improved Alternation Product
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 23-25, 2005
Generating a d-dimensional Linear Subspace Efficiently
Algorithmic Price Discrimination
Pull-based data broadcast with dependencies: be fair to users, not to items
The 2-Catalog Segmentation Problem
Viderman's algorithm for quantum LDPC codes
New Results on Server Problems
Separation and Approximation of Polyhedral Objects
Computing Square Colorings on Bounded-Treewidth and Planar Graphs
A face cover perspective to ℓ 1 embeddings of planar graphs
Implicit dictionaries supporting searches and amortized updates in O(log n log log n) time
Comparing the strength of query types in property testing: the case of testing k -colorability
On the compatibility of quartet trees
SoS Degree Reduction with Applications to Clustering and Robust Moment Estimation
Robust Clustering Oracle and Local Reconstructor of Cluster Structure of Graphs
Rumor Spreading and Vertex Expansion on Regular Graphs
Full Tilt: Universal Constructors for General Shapes with Uniform External Forces
Flipping Non-Crossing Spanning Trees
Pattern matching in dynamic texts
Planar Graphs in Blowups of Fans
Optimal Bound on the Combinatorial Complexity of Approximating Polytopes
An O (log k )-competitive algorithm for generalized caching
The Price of Information in Combinatorial Optimization
Testing for a theta
The Impacts of Dimensionality, Diffusion, and Directedness on Intrinsic Universality in the abstract Tile Assembly Model
Coloration Neighborhood Structures for General Graph Coloring
Simple Label-Correcting Algorithms for Partially Dynamic Approximate Shortest Paths in Directed Graphs
Nearly Optimal Planar k Nearest Neighbors Queries under General Distance Functions
Time vs. Information Tradeoffs for Leader Election in Anonymous Trees
Approximately counting and sampling small witnesses using a colourful decision oracle
Linear Diophantine Equations, Group CSPs, and Graph Isomorphism
Succinct geometric indexes supporting point location queries
Simpler algorithm for estimating frequency moments of data streams
New Diameter-Reducing Shortcuts and Directed Hopsets: Breaking the Barrier
Finding Triangles and Other Small Subgraphs in Geometric Intersection Graphs
Steiner Point Removal with Distortion O (log k )
Clustering Problems on Sliding Windows
Online story scheduling in web advertising
An Efficiently Computable Metric for Comparing Polygonal Shapes
Integrality Gaps for Random Integer Programs via Discrepancy
A fast generalized DFT for finite groups of Lie type
Faster Algorithms for Bounded-Difference Min-Plus Product
Map matching queries on realistic input graphs under the Fréchet distance
A Near-Linear Algorithm for the Planar Segment Center Problem
The Grid-Minor Theorem Revisited
Dynamic Algorithms for Packing-Covering LPs via Multiplicative Weight Updates
On the number of rectangular partitions
On binary searching with non-uniform costs
Online List Accessing Algorithms and Their Applications: Recent Empirical Evidence
On the costs and benefits of procrastination: approximation algorithms for stochastic combinatorial optimization problems
Experimental Study of Minimum Cut Algorithms
Superiority and complexity of the spaced seeds
Buy-at-Bulk Network Design: Approximating the Single-Sink Edge Installation Problem
Approximation algorithms for labeling hierarchical taxonomies
Beating Approximation Factor Two for Weighted Tree Augmentation with Bounded Costs
Improved approximation algorithms for broadcast scheduling
Equivalence Test for Read-Once Arithmetic Formulas
Min-max Partitioning of Hypergraphs and Symmetric Submodular Functions
New Algorithmic Aspects of the Local Lemma with Applications to Routing and Partitioning
Reconstruction of Depth-4 Multilinear Circuits
On Partitions and Presortedness of Sequences
Determinantal Sieving
Fault-tolerant facility location
A Lower Bound for Hellbronn's Triangle Problem in d Dimensions
A Size-Sensitive Discrepancy Bound for Set Systems of Bounded Primal Shatter Dimension
Spanning Circuits in Regular Matroids
The Complexity of Order Type Isomorphism
PageRank and the random surfer model
A simple entropy-based algorithm for planar point location
Preprocessing Imprecise Points for the Pareto Front
On finding exact solutions of linear programs in the oracle model
Hierarchical Shape Construction and Complexity for Slidable Polyominoes under Uniform External Forces
The stubborn problem is stubborn no more (a polynomial algorithm for 3-compatible colouring and the stubborn list partition problem)
The ( h , k )-Server Problem on Bounded Depth Trees
A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
Finite-resolution hidden surface removal
Cell probe lower bounds for succinct data structures
Stronger Privacy Amplification by Shuffling for Renyi and Approximate Differential Privacy
Thin graph classes and polynomial-time approximation schemes
Computing the distance between piecewise-linear bivariate functions
Balancing Notions of Equity: Trade-offs Between Fair Portfolio Sizes and Achievable Guarantees
An Improved Algorithm for Incremental Cycle Detection and Topological Ordering in Sparse Graphs
Efficient reductions among lattice problems
New Algorithms for Generating Conway Polynomials Over Finite Fields
Find Your Place: Simple Distributed Algorithms for Community Detection
Erdős-Pósa property of chordless cycles and its applications
The condensation transition in random hypergraph 2-coloring
On nash equilibria for a network creation game
The quantum Schur and Clebsch-Gordan transforms: I. efficient qudit circuits
Beating Greedy Matching in Sublinear Time
Shorter Labels for Routing in Trees
On approximating the depth and related problems
Testing Halfspaces over Rotation-Invariant Distributions
Leontief economies encode nonzero sum two-player games
Hallucination Helps: Energy Efficient Virtual Circuit Routing
Sparse Regular Expression Matching
Iterative Partial Rounding for Vertex Cover with Hard Capacities
Deterministic Edge Connectivity and Max Flow using Subquadratic Cut Queries
Impossibilities for Obviously Strategy-Proof Mechanisms
Shift Finding in Sub-Linear Time
On-Line Dynamic Programming with Applications to the Prediction of RNA Secondary Structure
A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Privacy
Windows scheduling as a restricted version of Bin Packing
Asynchronous 3-Majority Dynamics with Many Opinions
Computing the arrangement of curve segments: divide-and-conquer algorithms via sampling
Breaking 3-Factor Approximation for Correlation Clustering in Polylogarithmic Rounds
Broadcast scheduling: when fairness is fine
Distributed Maximal Independent Set using Small Messages
Subexponential parameterized algorithm for minimum fill-in
Improved Algorithms for Edit Distance and LCS: Beyond Worst Case
Non-migratory online deadline scheduling on multiprocessors
pBWT: Achieving Succinct Data Structures for Parameterized Pattern Matching and Related Problems
Approximating Local Homology from Samples
Efficient algorithms for document retrieval problems
Learning mixtures of structured distributions over discrete domains
A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum
Correlation-Robust Analysis of Single Item Auction
Fast Approximation Algorithm for Minimum Cost Multicommodity Flow
Revenue Maximization with an Uncertainty-Averse Buyer
Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth
Polynomial Planar Directed Grid Theorem
On extremal subgraphs of random graphs
Polynomial Time Algorithms to Find an Approximate Competitive Equilibrium for Chores
Error Amplification for Pairwise Spanner Lower Bounds
The On-Line d -Dimensional Dictionary Problem
Multi-Agent Combinatorial Contracts
Sharp Kernel Clustering Algorithms and Their Associated Grothendieck Inequalities
Stochastic analyses for online combinatorial optimization problems
Embedding k-outerplanar graphs into l1
Hill-climbing finds random planted bisections
Partial match queries in random quadtrees
The Data Broadcast Problem with Non-Uniform Transmission Rimes
Certificates in P and Subquadratic-Time Computation of Radius, Diameter, and all Eccentricities in Graphs
An Ω~(√log|T|) Lower Bound for Steiner Point Removal
Dynamic pricing for impatient bidders
Near-independence of permutations and an almost sure polynomial bound on the diameter of the symmetric group
Towards Optimal Deterministic Coding for Interactive Communication
Recovery and Rigidity in a Regular Stochastic Block Model
Optimal universal graphs with deterministic embedding
Splay trees, Davenport-Schinzel sequences, and the deque conjecture
Page Replacement for General Caching Problems
Increasing the Weight of Minimum Spanning Trees
Colouring Graphs with Prescribed Induced Cycle Lengths
Beating Greedy for Stochastic Bipartite Matching
On low dimensional local embeddings
A Better Approximation Algorithm for Finding Planar Subgraphs
Co-evolution of Opinion and Social Tie Dynamics Towards Structural Balance
Designing and learning optimal finite support auctions
Online and Bandit Algorithms Beyond ℓ p Norms
Approximating ( k, ℓ -Median Clustering for Polygonal Curves
Improved bounds for the unsplittable flow problem
A Two-pronged Progress in Structured Dense Matrix Vector Multiplication
Ultra-Fast Expected Time Parallel Algorithms
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019
Randomized Algorithms for Online Vector Load Balancing
On the diameter of the symmetric group: polynomial bounds
Learning the Fourier Spectrum of Probabilistic Lists and Trees
Scheduling Multicasts on Unit-Capacity Trees and Meshes
Robust algorithms for restricted domains
Traffic-redundancy aware network design
Line Traversals of Balls and Smallest Enclosing Cylinders in Three Dimensions
A subexponential lower bound for the Random Facet algorithm for Parity Games
Lower Bounds for Convexity Testing
Computational Geometry for Non-Geometers: Recent Developments on Some Classical Problems
A Fast Algorithm for Connecting Grid Points to the Boundary with Nonintersecting Straight Lines
Delaunay refinement for piecewise smooth complexes
Map Labeling and Its Generalizations
Island hopping and path colouring with applications to WDM network design
Optimizing misdirection
Approximating fractional hypertree width
A New Approximation Algorithm for the Planar Augmentation Problem
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014
2-Level Quasi-Planarity or How Caterpillars Climb (SPQR-)Trees
On AC 0 implementations of fusion trees and atomic heaps
Balls and bins models with feedback
Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games
Optimistic Sorting and Information Theoretic Complexity
A universally-truthful approximation scheme for multi-unit auctions
Improved Online Reachability Preservers
Instability of FIFO in the permanent sessions model at arbitrarily small network loads
Euclidean Bottleneck Steiner Tree is Fixed-Parameter Tractable
Testing k -Modal Distributions: Optimal Algorithms via Reductions
Graph Spanners by Sketching in Dynamic Streams and the Simultaneous Communication Model
Network design for information networks
Computing Height Persistence and Homology Generators in R 3 Efficiently
Deletion Without Rebalancing in Balanced Binary Trees
Polygon-containment and Translational min-Hausdorff-Distance between segment Sets are 3SUM-hard
Finding an induced path of given parity in planar graphs in polynomial time
Learning Markov networks: maximum bounded tree-width graphs
Lift and Project Algorithms for Precedence Constrained Scheduling to Minimize Completion Time
Approximate subset matching with Don't Cares
Differentially Private All-Pairs Shortest Path Distances: Improved Algorithms and Lower Bounds
Approximate Hypergraph Vertex Cover and generalized Tuza's conjecture
Cooperative Sharing and Asynchronous Consensus Using Single-Reader Single-Writer Registers
Uniformity Testing over Hypergrids with Subcube Conditioning
Space-efficient finger search on degree-balanced search trees
Reducing approximate Longest Common Subsequence to approximate Edit Distance
Known algorithms for EDGE CLIQUE COVER are probably optimal
Interpolation search for non-independent data
Fast SDP Algorithms for Constraint Satisfaction Problems
Randomized online algorithms for minimum metric bipartite matching
A Simple PTAS for the Dual Bin Packing Problem and Advice Complexity of Its Online Version
Decomposing a Graph Into Expanding Subgraphs
Tight Algorithms for Vertex Cover with Hard Capacities on Multigraphs and Hypergraphs
On deciding stability of scheduling policies in queueing systems
Competitive Implementation of Parallel Programs
Space-time tradeoffs for approximate spherical range counting
Testing and spot-checking of data streams (extended abstract)
Optimal Augmentation to Make a Graph k-Edge-Connected and Triconnected
Online Robust Mean Estimation
Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors
Efficient Routing and Scheduling Algorithms for Optical Networks
Noisy binary search and its applications
A determinant-based algorithm for counting perfect matchings in a general graph
Finding a Large Hidden Clique in a Random Graph
Improved Strongly Polynomial Algorithms for Deterministic MDPs, 2VPI Feasibility, and Discounted All-Pairs Shortest Paths
Improved Approximation Algorithms for Biconnected Subgraphs via Better Lower Bounding Techniques
Interactive Coding with Small Memory
Selective mapping: a discrete optimization approach to selecting a population subset for use in a high-density genetic mapping project
Computing Minimal Spanning Subgraphs in Linear Time
Fast edge orientation for unweighted graphs
Totally Unimodular Congestion Games
Efficiently decodable codes meeting Gilbert-Varshamov bound for low rates
Fixed-parameter tractability of DIRECTED MULTICUT with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation
An Improved Analysis of Greedy for Online Steiner Forest
A Fast Minimum Degree Algorithm and Matching Lower Bound
Linear equations with monomial constraints and decision problems in abelian-by-cyclic groups
Reordering Buffers with Logarithmic Diameter Dependency for Trees
List Decoding of Direct Sum Codes
Simplified kinetic connectivity for rectangles and hypercubes
Low-Rank PSD Approximation in Input-Sparsity Time
Compact Roundtrip Routing for Digraphs
A probabilistic analysis of a greedy algorithm arising from computational biology
Approximability and proof complexity
Representing dynamic binary trees succinctly
Separating stable sets in claw-free graphs via Padberg-Rao and compact linear programs
A Stackelberg Strategy for Routing Flow over Time
Greedy Local Improvement and Weighted Set Packing Approximation
On Page Migration and Other Relaxed Task Systems
Exact Solutions to Large-scale Plane Steiner Tree Problems
Gossip vs. Markov Chains, and Randomness-Efficient Rumor Spreading
Flow-Based Algorithms for Local Graph Clustering
Approximate Dynamic Programming using Halfspace Queries and Multiscale Monge Decomposition
Fast Distributed Brooks' Theorem
Learning Hard-Constrained Models with One Sample
Approximating the Statistics of various Properties in Randomly Weighted Graphs
A QPTAS for TSP with Fat Weakly Disjoint Neighborhoods in Doubling Metrics
Tight Bounds for the Distribution-Free Testing of Monotone Conjunctions
Decomposition, Approximation, and Coloring of Odd-Minor-Free Graphs
Hierarchy-Based Algorithms for Minimizing Makespan under Precedence and Communication Constraints
Incremental Evaluation of Computational Circuits
Edge dominating and hypomatchable sets
A randomized online algorithm for bandwidth utilization
Approximate Maximum Matching in Random Streams
Sequential cavity method for computing limits of the log-partition function for lattice models
Perron-Frobenius Theory in Nearly Linear Time: Positive Eigenvectors, M-matrices, Graph Kernels, and Other Applications
Parameterized Approximation for Capacitated d -Hitting Set with Hard Capacities
Efficient Pattern Matching with Scaling
Oblivious string embeddings and edit distance approximations