yusuke1997/dblp-id-title huggingface dataset:
Strictly non-blocking WDM cross-connects
The Angular-Metric Traveling Salesman Problem
Shortest Non-trivial Cycles in Directed and Undirected Surface Graphs
Interval Vertex Deletion Admits a Polynomial Kernel
Complex Semidefinite Programming and Max-k-Cut
Minimizing Channel Density by Lateral Shifting of Components
Discrete Gaussian Sampling Reduces to CVP and SVP
The Complexity of Counting Surjective Homomorphisms and Compactions
Lower Bounds for Sparse Recovery
Unique Games hardness of Quantum Max-Cut, and a conjectured vector-valued Borell's inequality
Worst case constant time priority queue
Algorithms for Ray Class Groups and Hilbert Class Fields
I/O-efficient algorithms for graphs of bounded treewidth
Subexponential parameterized algorithm for Interval Completion
Recognizing Balanced 0, +/- Matrices
Near-Optimal Range Reporting Structures for Categorical Data
A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size
MAX CUT in cubic graphs
Anytime algorithms for multi-armed bandit problems
Approximability of dense and sparse instances of minimum 2-connectivity, TSP and path problems
Passing the Limits of Pure Local Search for Weighted k -Set Packing
Space Lower Bounds for Approximating Maximum Matching in the Edge Arrival Model
LP Relaxations of Some NP-Hard Problems Are as Hard as Any LP
Submatrix maximum queries in Monge matrices and Monge partial matrices, and their applications
Two and Higher Dimensional Pattern Matching in Optimal Expected Time
Recognizing <italic>k</italic>-leaf powers in polynomial time, for constant <italic>k</italic>
Optimal Approximate Polytope Membership
Tight Hardness Results for Minimizing Discrepancy
Beating the Logarithmic Lower Bound: Randomized Preemptive Disjoint Paths and Call Control Algorithms
Fast distributed graph coloring with O(Delta) colors
Resource augmentation for weighted flow-time explained by dual fitting
On the Degree Distribution of Random Planar Graphs
Computation in Noisy Radio Networks
Tight approximation algorithms for maximum general assignment problems
I/O-efficient data structures for colored range and prefix reporting
A nearly 5/3-approximation FPT Algorithm for Min- k -Cut
A faster implementation of the Goemans-Williamson clustering algorithm
Deterministically Maintaining a (2 + ∊)-Approximate Minimum Vertex Cover in O(1/∊2) Amortized Update Time
Combinatorial Algorithm for Restricted Max-Min Fair Allocation
An FPTAS for the square lattice six-vertex and eight-vertex models at low temperatures
Rank/select operations on large alphabets: a tool for text indexing
Maximizing Bisubmodular and k -Submodular Functions
High-dimensional approximate r -nets
The Adversarial Noise Threshold for Distributed Protocols
Tight Bounds on the Number of Minimum-Mean Cycle Cancellations and Related Results
Dominating sets in planar graphs: branch-width and exponential speed-up
Cutting planes and the traveling salesman problem (abstract only)
Platforms for Efficient and Incentive-Aware Collaboration
A Combinatorial Algorithm for the Determinant
Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields
Parameterized Algorithm for the Disjoint Path Problem on Planar Graphs: Exponential in k 2 and Linear in n
A complexity dichotomy for hitting connected minors on bounded treewidth graphs: the chair and the banner draw the boundary
Arborescences, Colorful Forests, and Popularity
Oblivious routing on node-capacitated and directed graphs
Succinct approximate convex pareto curves
School Redistricting: Wiping Unfairness Off the Map
Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity
Partial and Constrained Level Planarity
Putting Off the Catching Up: Online Joint Replenishment Problem with Holding and Backlog Costs
MCMC sampling colourings and independent sets of G ( n, d / n ) near uniqueness threshold
Sensitivity Oracles for All-Pairs Mincuts
Efficiently list-edge coloring multigraphs asymptotically optimally
Algorithms for Implicit Hitting Set Problems
On incremental rendering of silhouette maps of polyhedral scene
Simulating Random Walks in Random Streams
Parameterized Algorithms for Constraint Satisfaction Problems Above Average with Global Cardinality Constraints
Constant Factor Approximation for Subset Feedback Set Problems via a new LP relaxation
Embedding metrics into ultrametrics and graphs into spanning trees with constant average distortion
Exact and efficient 2D-arrangements of arbitrary algebraic curves
The Maximum Number of Minimal Dominating Sets in a Tree
Planar Graphs as L-intersection or L-contact graphs
Testing Convex Truncation
Smaller core-sets for balls
Lower Bounds for Set Intersection Queries
Optimal angle bounds for Steiner triangulations of polygons
Tail Estimates for the Space Complexity of Randomized Incremental Algorithms
Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes
Approximation algorithms for wavelet transform coding of data streams
Special edges, and approximating the smallest directed k -edge connected spanning subgraph
Understanding Memory-Regret Trade-Off for Streaming Stochastic Multi-Armed Bandits
Self-Stabilizing Unidirectional Network Algorithms by Power-Supply (Extended Abstract)
Selecting the Median
A Topological Characterization of Modulo- p Arguments and Implications for Necklace Splitting
Algorithms for k-colouring and finding maximal independent sets
Linear equations, arithmetic progressions and hypergraph property testing
Incremental Topological Sort and Cycle Detection in Expected Total Time
The power of basis selection in fourier sampling: hidden subgroup problems in affine groups
Efficient estimation algorithms for neighborhood variance and other moments
The complexity of game dynamics: BGP oscillations, sink equilibria, and beyond
Approximating Maximum Independent Set in Bounded Degree Graphs
Adversarial deletion in a scale free random graph process
Cache-Oblivious and Data-Oblivious Sorting and Applications
Ring Routing and Wavelength Translation
The Impact of Heterogeneity and Geometry on the Proof Complexity of Random Satisfiability
Theoretical and Practical Aspects of Combinatorial Problem Solving
On the Structure of Unique Shortest Paths in Graphs
Improved Algorithms for Population Recovery from the Deletion Channel
Counting Homomorphic Cycles in Degenerate Graphs
Timeliness Through Telephones: Approximating Information Freshness in Vector Clock Models
Integer quadratic programming in the plane
(1 + Ω(1))-Αpproximation to MAX-CUT Requires Linear Space
A 3-Approximation Algorithm for Maximum Independent Set of Rectangles
Fairness in Scheduling
Tight Bounds for the Subspace Sketch Problem with Applications
Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025
On the Bidirected Cut Relaxation for the Metric Steiner Tree Problem
Practical Methods for Approximating Shortest Paths on a Convex Polytope in R 3
A certifying algorithm for the consecutive-ones property
Approximately Counting Hamilton Cycles in Dense Graphs
Embedding Planar Graphs into Graphs of Treewidth O (log 3 n )
An asymptotic approximation algorithm for 3D-strip packing
Simple Analyses of the Sparse Johnson-Lindenstrauss Transform
Commuting with delay prone buses
A Lower Bound for Jumbled Indexing
Arboricity and spanning-tree packing in random graphs with an application to load balancing
An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations
Robust Sparsification for Matroid Intersection with Applications
Dynamic optimality for skip lists and B-trees
Counting inversions in lists
Convergence, Stability, and Discrete Approximation of Laplace Spectra
Efficient bundle sorting
Approximation Algorithms for the Discrete Time-Cost Tradeoff Problem
Sparser Johnson-Lindenstrauss transforms
Simulating a stack using queues
Streaming Lower Bounds for Approximating MAX-CUT
Improved bounds on sorting with length-weighted reversals
Improved competitive ratio for the matroid secretary problem
Approximation hardness of optimization problems in intersection graphs of d -dimensional boxes
Analysis of a Simple Greedy Matching Algorithm on Random Cubic Graphs
Intrinsic universality in tile self-assembly requires cooperation
An Efficient Representation for Filtrations of Simplicial Complexes
The UGC hardness threshold of the ℓ p Grothendieck problem
Cake Cutting on Graphs: A Discrete and Bounded Proportional Protocol
Sparse Suffix Tree Construction in Optimal Time and Space
Reconstruction under outliers for Fourier-sparse functions
Rejecting jobs to Minimize Load and Maximum Flow-time
(Almost) Ruling Out SETH Lower Bounds for All-Pairs Max-Flow
A Polynomial-Time Approximation Scheme for Weighted Planar Graph TSP
Directed graphs requiring large numbers of shortcuts
An Improved Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market
Scheduling split intervals
An Efficient Parallel Algorithm that Finds Independent Sets of Guaranteed Size
A Naive Algorithm for Feedback Vertex Set
A Framework for Approximation Schemes on Disk Graphs
Estimating graph parameters via random walks with restarts
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 6-8, 2002, San Francisco, CA, USA
Spherical Discrepancy Minimization and Algorithmic Lower Bounds for Covering the Sphere
Algorithmic and Hardness Results for the Hub Labeling Problem
An Efficient Algorithm for the Vertex-Disjoint Paths Problem in Random Graphs
Better bounds for online load balancing on unrelated machines
Network sketching or: "How Much Geometry Hides in Connectivity?--Part II"
Erdös-Pósa property and its algorithmic applications: parity constraints, subset feedback set, and subset packing
On the Orbit Closure Containment Problem and Slice Rank of Tensors
Beating the Direct Sum Theorem in Communication Complexity with Implications for Sketching
Making data structures confluently persistent
Approximating minimum quartet inconsistency (abstract)
On the number of tetrahedra with minimum, unit, and distinct volumes in three-space
Optimal Constructions of Hybrid Algorithms
Fast zeta transforms for lattices with few irreducibles
Combinatorial Auctions via Posted Prices
On the discrepancy of random low degree set systems
Optimal space lower bounds for all frequency moments
Near-Optimal No-Regret Algorithms for Zero-Sum Games
Linear Programs for Randomized On-Line Algorithms
Web caching with request reordering
Improved Access to Optimal Bandwidth in Trees
On-line Approximate List Indexing with Applications
IMproved results for route planning in stochastic transportation
On the complexity of range searching among curves
Symmetric Polymorphisms and Efficient Decidability of Promise CSPs
Fast String Searching in Secondary Storage: Theoretical Developments And Experimental Results
The Power of Migration in Multi-Processor Scheduling of Real-Time Systems
Equivalence of local treewidth and linear local treewidth and its algorithmic applications
Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 28-30 January 1996, Atlanta, Georgia, USA
Shallow Excluded Minors and Improved Graph Decompositions
How to Meet Asynchronously (Almost) Everywhere
Submodular Maximization with Cardinality Constraints
Fair Price Discrimination
Welfare Maximization with Production Costs: A Primal Dual Approach
On the chromatic number of some geometric hypergraphs
Geometric clustering: fixed-parameter tractability and lower bounds with respect to the dimension
Fast, Deterministic and Sparse Dimensionality Reduction
The QRQW PRAM: Accounting for Contention in Parallel Algorithms
Robust Probabilistic Inference
Inferring tree topologies using flow tests
Quotient sparsification for submodular functions
Improved Bounds for Sampling Solutions of Random CNF Formulas
Robust hamiltonicity of random directed graphs extended abstract
Parallel processor scheduling with delay constraints
Efficient Generation of k-Directional Assembly Sequences
Compact labeling schemes for ancestor queries
Competitive Non-Preemptive Call Control
Theory of semidefinite programming for sensor network localization
Truthful Multi-Parameter Auctions with Online Supply: an Impossible Combination
Minimum weight convex Steiner partitions
Lower Bounds for Identifying Subset Members with Subset Queries
Simultaneous diagonal flips in plane triangulations
Fast Discrepancy Minimization with Hereditary Guarantees
Santa Claus meets Makespan and Matroids: Algorithms and Reductions
Sharp Bounds on Formation-free Sequences
Learning Hierarchical Cluster Structure of Graphs in Sublinear Time
An Efficient Algorithm for Computing the i th letter of 4 n a
Orthogonal graph drawing with constraints
Sweeping simple polygons with a chain of guards
PTASes for Euclidean TSP with Unit Disk and Unit Square Neighborhoods
Packing Small Vectors
Certifying large branch-width
On the bit-complexity of Lempel-Ziv compression
The Restricted Isometry Property of Subsampled Fourier Matrices
Algorithms to Approximate Column-Sparse Packing Problems
Windows scheduling problems for broadcast systems
A Framework for Parameterized Subexponential Algorithms for Generalized Cycle Hitting Problems on Planar Graphs
On Local Register Allocation
Phase Transition for the Mixing Time of the Glauber Dynamics for Coloring Regular Trees
Optimal Algorithms for Testing Closeness of Discrete Distributions
Minimum Common String Partition Parameterized by Partition Size Is Fixed-Parameter Tractable
Optimal Bounds for Johnson-Lindenstrauss Transforms and Streaming Problems with Sub-Constant Error
Persistent homology for kernels, images, and cokernels
Optimal randomized EREW PRAM Algorithms for Finding Spanning Forests and for other Basic Graph Connectivity Problems
Mutual Search (Extended Abstract)
A Tight VC-Dimension Analysis of Clustering Coresets with Applications
Placement Algorithms for Hierarchical Cooperative Caching
Approximation algorithms for the 0-extension problem
Deterministic random walks on regular trees
Fast and Accurate Approximations of the Optimal Transport in Semi-Discrete and Discrete Settings
Planar Geometric Location Problems and Maintaining the Width of a Planar Set
Polynomial Solvability of Variants of the Trust-Region Subproblem
Ancient and New Algorithms for Load Balancing in the L p Norm
An asymptotic approximation scheme for multigraph edge coloring
An Efficient Algorithm for Dynamic Text Indexing
A Primal-Dual Schema Based Approximation Algorithm for the Element Connectivity Problem
The Need for Seed (in the abstract Tile Assembly Model)
Approximating Watchman Routes
An experimental study of an opportunistic index
Fast Consensus via the Unconstrained Undecided State Dynamics
Algorithms for finding an induced cycle in planar graphs and bounded genus graphs
I/O-Efficient Algorithms for Contour-line Extraction and Planar Graph Blocking (Extended Abstract)
Perturbations and vertex removal in a 3D delaunay triangulation
X -Ramanujan graphs
Resilient search trees
Streaming algorithms for the missing item finding problem
The geometry of binary search trees
Earth mover distance over high-dimensional spaces
An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
Dimension reduction for ultrametrics
Sperner's Colorings, Hypergraph Labeling Problems and Fair Division
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22-25, 2023
Computing minimum cuts in hypergraphs
Coloring random graphs online without creating monochromatic subgraphs
Vertices of Degree k in Random Maps
A Tight Analysis of Greedy Yields Subexponential Time Approximation for Uniform Decision Tree
Maximally Recoverable LRCs: A field size lower bound and constructions for few heavy parities
Making deterministic signatures quickly
A new constructive root bound for algebraic expressions
Optimal Fully Dynamic k -Center Clustering for Adaptive and Oblivious Adversaries
Tight approximability of MAX 2-SAT and relatives, under UGC
Causal Erasure Channels
On distance to monotonicity and longest increasing subsequence of a data stream
Towards an SDP-based Approach to Spectral Methods: A Nearly-Linear-Time Algorithm for Graph Partitioning and Decomposition
An Infinite Class of Sparse-Yao Spanners
What are the Least Tractable Instances of max Independent Set?
The Effect of Sparsity on k -Dominating Set and Related First-Order Graph Properties
Matrix rounding and approximation
Using Network Flows for Surface Modeling
Finding large sticks and potatoes in polygons
4D Range Reporting in the Pointer Machine Model in Almost-Optimal Time
The Speed of Evolution
Computing Cut-Based Hierarchical Decompositions in Almost Linear Time
Geometric Optimization and Sums of Algebraic Functions
Coloring triangle-free graphs on surfaces
Optimal Good-Aspect-Ratio Coarsening for Unstructured Meshes
Approximation Algorithms and Hardness for Strong Unique Games
Efficient decoding up to a constant fraction of the code length for asymptotically good quantum codes
Recovering the original simplicity: succinct and deterministic quantum algorithm for the welded tree problem
On the Parsimonious Property of Connectivity Problems
Beyond Submodular Maximization via One-Sided Smoothness
Efficient Low-Redundancy Codes for Correcting Multiple Deletions
An online mechanism for ad slot reservations with cancellations
Stronger 3SUM-Indexing Lower Bounds
Tight bounds on the maximum size of a set of permutations with bounded VC-dimension
Improved bounds on the sample complexity of learning
Edge-disjoint paths in expanders: online with removals
Packing Random Items of Three Colors
Communication-Rounds Tradeoffs for Common Randomness and Secret Key Generation
Reconstructing Approximate Phylogenetic Trees from Quartet Samples
A simple algorithm for random colouring G ( n, d/n ) using (2 + ε) d colours
Inapproximability for Planar Embedding Problems
The matching polytope does not admit fully-polynomial size relaxation schemes
Sampling Spin Configurations of an Ising System
Approximating matching size from random streams
Distributed admission control, scheduling, and routing with stale information
New Approximation Techniques for Some Ordering Problems
Online Generalized Network Design Under (Dis)Economies of Scale
On Distances between Phylogenetic Trees (Extended Abstract)
Faster Deterministic and Las Vegas Algorithms for Offline Approximate Nearest Neighbors in High Dimensions
Time-Space Tradeoffs for Element Distinctness and Set Intersection via Pseudorandomness
Improved upper bounds for Random-Edge and Random-Jump on abstract cubes
Phase Transitions in Random Dyadic Tilings and Rectangular Dissections
Constant factor approximation algorithm for the knapsack median problem
Linear-size approximate voronoi diagrams
Algorithms and Adaptivity Gaps for Stochastic Probing
Communication complexity of document exchange
Simplex Transformations and the Multiway Cut Problem
Morphing orthogonal planar graph drawings
Strictly convex drawings of planar graphs
A fully combinatorial algorithm for submodular function minimization
Global minimum cuts in surface embedded graphs
Two New Upper Bounds for SAT
Length-Limited Coding
Forbidden structure characterization of circular-arc graphs and a certifying recognition algorithm
Fixed-Price Approximations in Bilateral Trade
Approximating the minimum strongly connected subgraph via a matching lower bound
A practical algorithm for recovering the best supported edges of an evolutionary tree (extended abstract)
A Tight Bound for Testing Partition Properties
Perfect Arborescence Packing in Preflow Mincut Graphs
Rapid mixing of Gibbs sampling on graphs that are sparse on average
Lift-and-Project Integrality Gaps for Santa Claus
Efficient algorithms for the 2-gathering problem
Grammar Boosting: A New Technique for Proving Lower Bounds for Computation over Compressed Data
Approximating Subset Sum Ratio faster than Subset Sum
Analyzing Boolean functions on the biased hypercube via higher-dimensional agreement tests: [Extended abstract]
Space complexity of list H -colouring: a dichotomy
Packing Short Cycles
Economical Convex Coverings and Applications
Linear Recognition of Almost Interval Graphs
A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
Solving 1-Laplacians in Nearly Linear Time: Collapsing and Expanding a Topological Ball
A 1.598 Approximation Algorithm for the Steiner Problem in Graphs
Locally Efficient On-Line Strategies for Routing Packets Along Fixed Paths
Approximation schemes for multidimensional packing
Frugal path mechanisms
5-coloring K 3, k -minor-free graphs: Beyond Thomassen
Approximating the Distance to Monotonicity of Boolean Functions
Congestion-Approximators from the Bottom Up
Paging and list update under bijective analysis
Twisted Tabulation Hashing
Fully Dynamic Consistent k -Center Clustering
Reconstructing a collection of curves with corners and endpoints
A quadratic kernel for feedback vertex set
An algorithmic framework for obtaining lower bounds for random Ramsey problems extended abstract
Group Signatures Á la carte
A Subquadratic-Time Algorithm for Decremental Single-Source Shortest Paths
Optimal Distributed Coloring Algorithms for Planar Graphs in the LOCAL model
Lower bounds for external memory dictionaries
Sketching for M -Estimators: A Unified Approach to Robust Regression
Optimal Construction of Compressed Indexes for Highly Repetitive Texts
Frequency Estimation with One-Sided Error
Near-Optimal Light Spanners
Minimum Forcing Sets for Miura Folding Patterns
New constructions of (alpha, beta)-spanners and purely additive spanners
Locally lifting the curse of dimensionality for nearest neighbor search (extended abstract)
Distance in the Forest Fire Model How far are you from Eve?
Planar graphs are in 1-STRING
Reducing Revenue to Welfare Maximization: Approximation Algorithms and other Generalizations
A linear time algorithm for seeds computation
Voronoi Diagrams of Lines in 3-Space Under Polyhedral Convex Distance Functions
A Framework for the Secretary Problem on the Intersection of Matroids
The Simplex Algorithm is NP-mighty
Scheduling protocols for switches with large envelopes
Bayesian Incentive Compatibility via Fractional Assignments
Influence Maximization in Undirected Networks
Spectral Clustering Oracles in Sublinear Time
Subquadratic time approximation algorithms for the girth
Computational Experience with an Approximation Algorithm on Large-Scale Euclidean Matching Instances
Weakly chordal graph algorithms via handles
Tight Bounds for Graph Homomorphism and Subgraph Isomorphism
New approximability and inapproximability results for 2-dimensional Bin Packing
Nearly Tight Oblivious Subspace Embeddings by Trace Inequalities
An FPT Algorithm Beating 2-Approximation for k -Cut
Explicit constructions for compressed sensing of sparse signals
The hidden subgroup problem and permutation group theory
Fully Dynamic (Δ + 1)-Coloring Against Adaptive Adversaries
Correlation Decay up to Uniqueness in Spin Systems
Data migration to minimize the average completion time
Improved List Size for Folded Reed-Solomon Codes
A dynamic model of barter exchange
On Primal-Dual Circle Representations
Algorithms for Dynamic Closest Pair and n-Body Potential Fields
Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes
Maintaining all-pairs approximate shortest paths under deletion of edges
Queries with Segments in Voronoi Diagrams
Optimal scale-free compact routing schemes in networks of low doubling dimension
A tree-edit-distance algorithm for comparing simple, closed shapes
Vector clique decompositions
Matrix Balancing in L p Norms: Bounding the Convergence Rate of Osborne's Iteration
The diameter of a long range percolation graph
Rumour Spreading and Graph Conductance
Approximation Algorithms for Precedence-Constrained Scheduling Problems on Parallel Machines That Run at Fifferent Speeds (Extended Abstract)
Few Matches or Almost Periodicity: Faster Pattern Matching with Mismatches in Compressed Texts
A Polynomial Time Primal Network Simplex Algorithm for Minimum Cost Flows (An Extended Abstract)