yusuke1997/dblp-id-title huggingface dataset:
Exponential Time Improvement for min-wise Based Algorithms
Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs
Improved Distributed Network Decomposition, Hitting Sets, and Spanners, via Derandomization
Polynomial Time Algorithms for Some Evacuation Problems
Canonical Paths for MCMC: from Art to Science
Maintaining the Minimal Distance of a Point Set in Polylogarithmic Time
All-pairs bottleneck paths in vertex weighted graphs
Shape sensitive geometric permutations
Distributed Backup Placement in One Round and its Applications to Maximum Matching Approximation and Self-Stabilization
Fast Construction of Irreducible Polynomials over Finite Fields
Beating the 2 Delta Bound for Approximately Counting Colourings: A Computer-Assisted Proof of Rapid Mixing
New Lower Bounds for the Number of Pseudoline Arrangements
Exponentially Improved Algorithms and Lower Bounds for Testing Signed Majorities
A (1 + 1/e)-Approximation Algorithm for Maximum Stable Matching with One-Sided Ties and Incomplete Lists
Adjacency Sketches in Adversarial Environments
Dynamic Consistent k -Center Clustering with Optimal Recourse
Shrunk subspaces via operator Sinkhorn iteration
Stochastic ℓp Load Balancing and Moment Problems via the L-Function Method
The complexity of conservative valued CSPs
Tight Lower Bound on Equivalence Testing in Conditional Sampling Model
Approximating rooted Steiner networks
Approximation algorithms for the metric labeling problem via a new linear programming formulation
Efficient algorithms for substring near neighbor problem
Some Graphic Uses of an Even Number of Odd Nodes
Coding against deletions in oblivious and online models
On a combinatorial generation problem of Knuth
Selling Information Through Consulting
Incidence Geometries and the Pass Complexity of Semi-Streaming Set Cover
Design of Practical and Provably Good Random Number Generators (Extended Abstract)
Non-convex Compressed Sensing with the Sum-of-Squares Method
Morphing between polylines
Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H -free graphs
New Explicit Constant-Degree Lossless Expanders
Scheduling Unrelated Machines with Costs
LAND: stretch (1 + epsilon) locality-aware networks for DHTs
Succinct representations of lcp information and improvements in the compressed suffix arrays
Random lifts of graphs
Edge Expansion and Spectral Gap of Nonnegative Matrices
Polynomial Kernels and Wideness Properties of Nowhere Dense Graph Classes
Fluid Limits, Bin Packing, and Stochastic Analysis of Algorithms
Scaling Algorithms for Weighted Matching in General Graphs
Player-optimal Stable Regret for Bandit Learning in Matching Markets
Robust Price of Anarchy Bounds via LP and Fenchel Duality
Implicit Flow Routing on Terrains with Applications to Surface Networks and Drainage Structures
Completeness for First-Order Properties on Sparse Structures with Algorithmic Applications
Covering minimum spanning trees of random subgraphs
The effect of induced subgraphs on quasi-randomness
Property testing of data dimensionality
Efficient Broadcast on Random Geometric Graphs
The effects of temporary sessions on network performance
Finding Four-Node Subgraphs in Triangle Time
Nearly Tight Bounds for Testing Function Isomorphism
Parameters of Two-Prover-One-Round Game and The Hardness of Connectivity Problems
The Complexity of Distributed Edge Coloring with Small Palettes
Adaptive intersection and t-threshold problems
Cache-Adaptive Algorithms
On the random 2-stage minimum spanning tree
Non-linear Hamilton cycles in linear quasi-random hypergraphs
Approximation Algorithms for Curvature-Constrained Shortest Paths
Positivity of the symmetric group characters is as hard as the polynomial time hierarchy
A Note on Max k-Vertex Cover: Faster FPT-AS, Smaller Approximate Kernel and Improved Approximation
Dimension detection via slivers
Maximum independent set of rectangles
Even maps, the Colin de Verdière number and representations of graphs
Compact LP Relaxations for Allocation Problems
Road Network Reconstruction for Organizing Paths
Persistent Path Homology of Directed Networks
Online Weighted Matching with a Sample
Clustering time series under the Fréchet distance
Minimizing Message Size in Stochastic Communication Patterns: Fast Self-Stabilizing Protocols with 3 bits
Embedding Planar Graphs into Low-Treewidth Graphs with Applications to Efficient Approximation Schemes for Metric Problems
Correlation Clustering with Noisy Input
Steiner Connectivity Augmentation and Splitting-off in Poly-logarithmic Maximum Flows
Cache oblivious search trees via binary trees of small height
Finding the shortest bottleneck edge in a parametric minimum spanning tree
The traveling salesman problem for lines, balls and planes
Moser-Tardos Algorithm: Beyond Shearer's Bound
Can We Overcome the n log n Barrier for Oblivious Sorting?
Multiplicative Rank-1 Approximation using Length-Squared Sampling
Tight lower bounds for selection in randomly ordered streams
Improved lower and upper bounds for universal TSP in planar metrics
Deterministic construction of an approximate M-ellipsoid and its applications to derandomizing lattice algorithms
Connectivity Oracles for Graphs Subject to Vertex Failures
Wavelength Conversion in Optical Networks
Computing the quartet distance between evolutionary trees
The stable set problem in graphs with bounded genus and bounded odd cycle packing number
Pattern Matching in a Digitized Image
Approximation Algorithms for Stochastic Boolean Function Evaluation and Stochastic Submodular Set Cover
Counting Small Permutation Patterns
Approximating Knapsack and Partition via Dense Subset Sums
The complexity of independent set reconfiguration on bipartite graphs
On the Complexity of Time-Dependent Shortest Paths
Bounding Variance and Expectation of Longest Path Lengths in DAGs
Analysis of greedy approximations with nonsubmodular potential functions
On the Computational Complexity of Betti Numbers: Reductions from Matrix Rank
Sandpile prediction on a tree in near linear time
A robust maximum completion time measure for scheduling
An Improved Local Search Algorithm for k-Median
Block-Structured Integer and Linear Programming in Strongly Polynomial and Near Linear Time
Approximating the Girth
Optimal Multichannel Communication Under Failure
Reporting neighbors in high-dimensional Euclidean spaces
Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance
Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings
Approximating the Crossing Number of Graphs Embeddable in Any Orientable Surface
Compatible Connectivity-Augmentation of Planar Disconnected Graphs
A 3/2-Approximation Algorithm for Sorting by Reversals
Online Interval Scheduling
Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds
On the Hardness of PosSLP
Wireless Capacity with Oblivious Power in General Metrics
The k -orientability thresholds for G n, p
Quantum tomography using state-preparation unitaries
(1 + ∊)-Approximate f -Sensitive Distance Oracles
Improved Bounds for All Optical Routing
Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter
k-Servers with a Smile: Online Algorithms via Projections
Connectivity in bridge-addable graph classes: the McDiarmid-Steger-Welsh conjecture
Computing Circle Packing Representations of Planar Graphs
Approximability of Robust Network Design
Bounds for Random Constraint Satisfaction Problems via Spatial Coupling
Minimum d -dimensional arrangement with fixed points
Parameterized Pattern Matching by Boyer-Moore-Type Algorithms
On the complexity of Nash equilibria of action-graph games
On a linear program for minimum-weight triangulation
Inverse Inbreeding Coefficient Problems with an Application to Linkage Analysis of Recessive Diseases in Inbred Populations
Maximal Empty Ellipsoids
Seeded Graph Matching via Large Neighborhood Statistics
LBFS Orderings and Cocomparability Graphs
A Cut-Matching Game for Constant-Hop Expanders
Pattern Matching on Grammar-Compressed Strings in Linear Time
Approximately Sampling Elements with Fixed Rank in Graded Posets
On RAM Priority Queues
A Better Approximation Ratio for the Minimum k-Edge-Connected Spanning Subgraph Problem
Cache Performance Analysis of Traversals and Random Accesses
Lower Bounds for Edit Distance and Product Metrics via Poincaré-Type Inequalities
A Fourier Space Algorithm for Solving Quadratic Assignment Problems
Computing contour trees in all dimensions
A polynomial-time approximation scheme for Steiner tree in planar graphs
Simpler, faster and shorter labels for distances in graphs
Algebraic Algorithms for Linear Matroid Parity Problems
External memory BFS on undirected graphs with bounded degree
A new algorithm for normal dominance constraints
Incremental Algorithms for Minimal Length Paths
Trace reconstruction with constant deletion probability and related results
Partial Resampling to Approximate Covering Integer Programs
Combinatorial Gap Theorem and Reductions between Promise CSPs
On Constant Multi-Commodity Flow-Cut Gaps for Families of Directed Minor-Free Graphs
Auctions for structured procurement
On the communication and streaming complexity of maximum bipartite matching
Balls and bins with structure: balanced allocations on hypergraphs
Concentration of polynomial random matrices via Efron-Stein inequalities
Distance labeling in graphs
Distributed Triangle Detection via Expander Decomposition
Manifold reconstruction from point samples
A constant approximation algorithm for the one-warehouse multi-retailer problem
Strongly Polynomial Frame Scaling to High Precision
Minimum Cut of Directed Planar Graphs in O ( n log log n ) Time
Dynamic Algorithms for Graph Coloring
Temporary tasks assignment resolved
Uncertainty about Uncertainty: Optimal Adaptive Algorithms for Estimating Mixtures of Unknown Coins
Online Scalable Scheduling for the ℓk-norms of Flow Time Without Conservation of Work
Solving Simple Stochastic Tail Games
Resource Minimization for Fire Containment
Google's Auction for TV Ads
Fully Dynamic Shortest Path Reporting Against an Adaptive Adversary
Just Take the Average! An Embarrassingly Simple 2^n-Time Algorithm for SVP (and CVP)
O (log log n )-competitive dynamic binary search trees
Fixed-Parameter Tractability of Hedge Cut
Elastic Caching
The Identity Problem in nilpotent groups of bounded class
Simple Markov-Chain Algorithms for Generating Bipartite Graphs and Tournaments (Extended Abstract)
An Improved Construction of Progression-Free Sets
Halving by a Thousand Cuts or Punctures
Triangulation Refinement and Approximate Shortest Paths in Weighted Regions
Certifying and repairing solutions to large LPs how good are LP-solvers?
The Quickest Transshipment Problem
Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless APSP can)
Multiscale Mapper: Topological Summarization via Codomain Covers
An optimal randomized algorithm for maximum Tukey depth
4-connected projective-planar graphs are hamiltonian-connected
Normalizers and permutational isomorphisms in simply-exponential time
Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
Preemptive Scheduling with Job-Dependent Setup Times
Dynamic Task Allocation in Asynchronous Shared Memory
Segmentation of Trajectories for Non-Monotone Criteria
Rationality-Robust Information Design: Bayesian Persuasion under Quantal Response
Markov Chains for Linear Extensions, the Two-Dimensional Case
Metric Violation Distance: Hardness and Approximation
Short Paths on the Voronoi Graph and Closest Vector Problem with Preprocessing
Dynamic Algebraic Algorithms
More Efficient Approximate k -wise Independent Permutations from Random Reversible Circuits via log-Sobolev Inequalities
Untangling Graphs on Surfaces
In-place 2-d nearest neighbor search
Approximate Distance Oracles for Planar Graphs with Subpolynomial Error Dependency
Privacy-preserving group data access via stateless oblivious RAM simulation
Graph Classes with Few Minimal Separators. I. Finite Forbidden Induced Subgraphs
On Locating Paths in Compressed Tries
The extended k -tree algorithm
Estimating DNA sequence entropy
Global Min-cuts in RNC, and Other Ramifications of a Simple Min-Cut Algorithm
Exponential Lower Bounds on Spectrahedral Representations of Hyperbolicity Cones
Ultimate greedy approximation of independent sets in subcubic graphs
New and improved algorithms for minsum shop scheduling
Estimating the Nash Social Welfare for coverage and other submodular valuations
Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model
Online Pricing with Impatient Bidders
A local algorithm for finding dense subgraphs
Approximating Cycles in Directed Graphs: Fast Algorithms for Girth and Roundtrip Spanners
Almost Tight Bounds for Online Facility Location in the Random-Order Model
On Finding Minimal 2-Connected Subgraphs
Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions
Labeling schemes for flow and connectivity
On testable properties in bounded degree graphs
On the Fine-Grained Complexity of the Unbounded SubsetSum and the Frobenius Problem
I/O-Efficient Dynamic Point Location in Monotone Planar Subdivisions
Set Cover in Sub-linear Time
Lower bounds for external algebraic decision trees
Certifying algorithms for recognizing interval graphs and permutation graphs
Eulerian Graph Sparsification by Effective Resistance Decomposition
Byzantine Agreement with Optimal Resilience via Statistical Fraud Detection
An Efficient Algorithm for the Three-Dimensional Diameter Problem
Competitive queueing policies for QoS switches
Linear programming and unique sink orientations
Simplex Range Searching Revisited: How to Shave Logs in Multi-Level Data Structures
Query Complexity of the Metric Steiner Tree Problem
Online Throughput-Competitive Algorithm for Multicast Routing and Admission Control
Approximating coloring and maximum independent sets in 3-uniform hypergraphs
Algorithms for combining rooted triplets into a galled phylogenetic network
On Uniform Capacitated k -Median Beyond the Natural LP Relaxation
Minimizing Weighted Completion Time on a Single Machine
Random graphs
Efficient oblivious transfer protocols
The string edit distance matching problem with moves
Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion
Approximation of functions over redundant dictionaries using coherence
Using Stopping Times to Bound Mixing Times
On the K -simple shortest paths problem in weighted directed graphs
Rumor spreading and vertex expansion
A New Approach to Parallel Computation of Polynomial GCD and to Related Parallel Computations over Fields and Integer Rings
Approximation schemes for Metric Bisection and partitioning
Combinatorial generation via permutation languages
New Approximation Algorithms for Minimum Enclosing Convex Shapes
Collecting weighted items from a dynamic queue
Efficient fully dynamic elimination forests with applications to detecting long paths and cycles
Anonymous Meeting in Networks
An algebraic method to compute a shortest path of local flips between two tilings
Counting without sampling: new algorithms for enumeration problems using statistical physics
Query strategies for priced information, revisited
Scheduling Malleable and Nonmalleable Parallel Tasks
Internal Pattern Matching Queries in a Text and Applications
Local homology transfer and stratification learning
Fully polynomial time approximation schemes for stochastic dynamic programs
Maintaining Dynamic Sequences Under Equality-Tests in Polylogarithmic Time
Matroid Secretary Problem in the Random Assignment Model
Local Smoothness and the Price of Anarchy in Atomic Splittable Congestion Games
Linear Time Parameterized Algorithms via Skew-Symmetric Multicuts
A dynamic programming approach to de novo peptide sequencing via tandem mass spectrometry
Sparse distance preservers and additive spanners
Learning-Augmented Weighted Paging
Data Structures for Range Minimum Queries in Multidimensional Arrays
Integrality Gaps and Approximation Algorithms for Dispersers and Bipartite Expanders
A near-optimal algorithm for computing the entropy of a stream
Sequential measurements, disturbance and property testing
Folding and One Straight Cut Suffice
Playing Twenty Questions with a Procrastinator
Maximum overhang
LP Relaxation and Tree Packing for Minimum k-cuts
A New Way to Use Semidefinite Programming with Applications to Linear Equations mod p
Online Multiserver Convex Chasing and Optimization
Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity, Unateness, and Juntas
Cheap labor can be expensive
An Analysis of Some Heuristics for the Maximum Planar Subgraph Problem
Optimizing markov models with applications to triangular connectivity coding
Finding a latent k -simplex in O * ( k · nnz(data)) time via Subset Smoothing
Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting
Meta-theorems for Parameterized Streaming Algorithms‡
On the Tractability of Public Persuasion with No Externalities
Self-Stabilizing Clock Synchronization with 1-bit Messages
Maximal biconnected subgraphs of random planar graphs
A Constant Factor Approximation Algorithm for Generalized Min-Sum Set Cover
A Deterministic Approximation Algorithm for a Minmax Integer Programming Problem
On the maximum quartet distance between phylogenetic trees
Fast Modular Subset Sum using Linear Sketching
A New Lower Bound on Hadwiger-Debrunner Numbers in the Plane
Characterization of cutoff for reversible Markov chains
Majorized Bayesian Persuasion and Fair Selection
Efficient dynamic traitor tracing
Pricing multicasting in more practical network models
SETH Says: Weak Fréchet Distance is Faster, but only if it is Continuous and in One Dimension
Cactus Representations in Polylogarithmic Max-flow via Maximal Isolating Mincuts
A deterministic subexponential algorithm for solving parity games
Counting matchings in irregular bipartite graphs and random lifts
PTAS for Maximum Weight Independent Set Problem with Random Weights in Bounded Degree Graphs
Dynamic (1 + ∊)-Approximate Matchings: A Density-Sensitive Approach
Rapid Mixing from Spectral Independence beyond the Boolean Domain
Shape matching using edit-distance: an implementation
The cover time of random geometric graphs
Recovering Evolutionary Trees Through Harmonic Greedy Triplets
On multiplicative λ-approximations and some geometric applications
The Asymmetric Traveling Salesman Problem on Graphs with Bounded Genus
Competitive Online Search Trees on Trees
Matching Nuts and Bolts
On Efficient Distance Approximation for Graph Properties
Minimum Fill-In: Inapproximability and Almost Tight Lower Bounds
Improved hardness for H -colourings of G -colourable graphs
Combinatorial algorithms for wireless information flow
Optimal dynamic vertical ray shooting in rectilinear planar subdivisions
An improved approximation algorithm for the column subset selection problem
Sublinear-Time Algorithms for Max Cut, Max E2Lin( q ), and Unique Label Cover on Expanders
Counting Stars and Other Small Subgraphs in Sublinear Time
Selective families, superimposed codes, and broadcasting on unknown radio networks
Convergence of Incentive-Driven Dynamics in Fisher Markets
Linear and O(n log n) Time Minimum-Cost Matching Algorithms for Quasi-Convex Tours
The Streaming Complexity of Cycle Counting, Sorting by Reversals, and Other Problems
Succinct indexable dictionaries with applications to encoding k-ary trees and multisets
Beating (1 - 1/e)-Approximation for Weighted Stochastic Matching
Error-Resilient DNA Computation
Scheduling precedence-constrained jobs with stochastic processing times on parallel machines
Computing optimal alpha-fat and alpha-small decompositions
Provably good multicore cache performance for divide-and-conquer algorithms
A Unified Approach to Dynamic Point Location, Ray Shooting, and Shortest Paths in Planar Maps
Improved Shortest Path Restoration Lemmas for Multiple Edge Failures: Trade-offs Between Fault-tolerance and Subpaths
Energy efficient online deadline scheduling
Optimal Distribution-Free Sample-Based Testing of Subsequence-Freeness
Flip Graph Connectivity for Arrangements of Pseudolines and Pseudocircles
Streaming k-means on Well-Clusterable Data
Enumerating k-SAT functions
A polynomial-time OPT ɛ -approximation algorithm for maximum independent set of connected subgraphs in a planar graph
Information Retrieval Algorithms: A Survey
A 1.875: approximation algorithm for the stable marriage problem
Extremal and probabilistic results for order types
Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs
Limitations on Testable Affine-Invariant Codes in the High-Rate Regime
Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable
Zeros of Holant problems: locations and algorithms
Improved Algorithms for Low Rank Approximation from Sparsity
Online topological ordering
Nested Quantum Walks with Quantum Data Structures
Linear-Sized Sparsifiers via Near-Linear Time Discrepancy Theory
Average-Case Hardness of Parity Problems: Orthogonal Vectors, k-SUM and More
Maximum-likelihood decoding of Reed-Solomon codes is NP-hard
Optimal rates for ranking a permuted isotonic matrix in polynomial time
On independent sets in random graphs
Testing Low Complexity Affine-Invariant Properties
Approximating independent sets in sparse graphs
The cover time of sparse random graphs
Traversing the FFT Computation Tree for Dimension-Independent Sparse Fourier Transforms
Incremental SSSP for Sparse Digraphs Beyond the Hopset Barrier
Tight Distributed Listing of Cliques
Optimal Prediction for Prefetching in the Worst Case
Dotted interval graphs and high throughput genotyping
Using Optimization to Obtain a Width-Independent, Parallel, Simpler, and Faster Positive SDP Solver
Optimization Problems Related to Zigzag Pocket Machining (Extended Abstract)
Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut
Fast convergence of selfish rerouting
Opting Into Optimal Matchings
Near-Optimal Relative Error Streaming Quantile Estimation via Elastic Compactors
K-pair delay constrained minimum cost routing in undirected networks
Ordering by weighted number of wins gives a good ranking for weighted tournaments
Shortest Paths in a Hybrid Network Model
A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between
Multi-unit Supply-monotone Auctions with Bayesian Valuations
Confronting hardness using a hybrid approach
Decomposition of multiple coverings into more parts
Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm
A Simple Provable Algorithm for Curve Reconstruction
Computing in continuous space with self-assembling polygonal tiles (extended abstract)
Multiple source shortest paths in a genus g graph
Optimal Placement of Convex Polygons to Maximize Point Containment
Primal Dual Gives Almost Optimal Energy Efficient Online Algorithms
Iterated Nearest Neighbors and Finding Minimal Polytopes
Evolutionary Dynamics in Finite Populations Mix Rapidly
A polylogarithmic space deterministic streaming algorithm for approximating distance to monotonicity
Inapproximability of Maximum Diameter Clustering for Few Clusters
A (2 + ∊)-Approximation for Maximum Weight Matching in the Semi-Streaming Model
Approximating the smallest k -edge connected spanning subgraph by LP-rounding
Robust algorithms with polynomial loss for near-unanimity CSPs
Zigzag Persistence via Reflections and Transpositions
Faster Vizing and Near-Vizing Edge Coloring Algorithms
Unconditionally reliable message transmission in directed networks
The Growth Rate of Vertex-Transitive Planar Graphs
Low Degree Local Correction Over the Boolean Cube
Practical approximation algorithms for zero- and bounded-skew trees
LP-based Analysis of Greedy-dual-size
Polyhedral Value Iteration for Discounted Games and Energy Games
Selecting Training Inputs via Greedy Rank Covering
Online scheduling with general cost functions
Approximation algorithms for node-weighted buy-at-bulk network design
An Efficient ∊ -BIC to BIC Transformation and Its Application to Black-Box Reduction in Revenue Maximization
Planar Negative k -Cycle