yusuke1997/dblp-id-title huggingface dataset:
Stability preserving transformations: packet routing networks with edge capacities and speeds
On the Unreasonable Effectiveness of Single Vector Krylov Methods for Low-Rank Approximation
On the Complexity of Computing an Equilibrium in Combinatorial Auctions
Real scaled matching
Cache-oblivious string dictionaries
Testing halfspaces
An exact subexponential-time lattice algorithm for Asian options
Streaming and sublinear approximation of entropy and information distances
Tight Bounds for Approximate Near Neighbor Searching for Time Series under the Fréchet Distance
Hardness of Approximation for Morse Matching
Learning from satisfying assignments
Polynomial interpolation from multiples
Quantum property testing
An optimal Bloom filter replacement
Subexponential parameterized algorithms on graphs of bounded-genus and H -minor-free graphs
New ( α, β ) Spanners and Hopsets
Generalized Preconditioning and Undirected Minimum-Cost Flow
The Complexity of Optimal Mechanism Design
Patience is a Virtue: The Effect of Slack on Competitiveness for Admission Control
Exponential lower bounds and integrality gaps for tree-like Lovász-Schrijver procedures
Fast algorithms for (max, min)-matrix multiplication and bottleneck shortest paths
An optimal algorithm for checking regularity (extended abstract)
A Time-Optimal Randomized Parallel Algorithm for MIS
Hardness of Approximation for Orienteering with Multiple Time Windows
Online budgeted matching in random input models with applications to Adwords
Delaunay triangulation programs on surface data
Computing maximally separated sets in the plane and independent sets in the intersection graph of unit disks
The Advantages of Forward Thinking in Generating Rooted and Free Trees
Computing equilibria for congestion games with (im)perfect information
The Multiple-Orientability Thresholds for Random Hypergraphs
Finding the closest lattice vector when it's unusually close
Anisotropic surface meshing
Simplified and Space-Optimal Semi-Streaming (2+epsilon)-Approximate Matching
Better online buffer management
Flows over time with load-dependent transit times
Accelerating simulated annealing for the permanent and combinatorial counting problems
Kernelization of packing problems
Data Structures for Weighted Matching and Nearest Common Ancestors with Linking
Deterministic Algorithms for Low Degree Factors of Constant Depth Circuits
External-memory exact and approximate all-pairs shortest-paths in undirected graphs
Beyond Locality-Sensitive Hashing
A combinatorial algorithm for computing a maximum independent set in a t-perfect graph
Online Scheduling via Learned Weights
I/O-Efficient Algorithms for Topological Sort and Related Problems
Improved Approximation Algorithms for the Minimum Latency Problem via Prize-Collecting Strolls
Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes
A Fast Approximation for Maximum Weight Matroid Intersection
Clock Auctions Augmented with Unreliable Advice
On Degeneracy in Geometric Computations
Polynomial Methods for Separable Convex Optimization in Unimodular Spaces
A Tale of Santa Claus, Hypergraphs and Matroids
The power of memory in randomized broadcasting
Lyndon words with a fixed standard right factor
Optimal Node-Degree Bounds for the Complexity of Nonplanarity Parameters
Gap Amplification for Reconfiguration Problems
Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007
Sparse Approximation via Generating Point Sets
Outperforming LRU via competitive analysis on parametrized inputs for paging
On Estimating Maximum Matching Size in Graph Streams
Jaywalking your dog: computing the Fréchet distance with shortcuts
Approximate Local Decoding of Cubic Reed-Muller Codes Beyond the List Decoding Radius
Conflict-free hypergraph matchings
NP-hardness of broadcast scheduling and inapproximability of single-source unsplittable min-cost flow
Cutting corners cheaply, or how to remove Steiner points
Theorems of Carathéodory, Helly, and Tverberg without dimension
Confluently Persistent Deques via Data Structural Bootstrapping
Exact Arithmetic at Low Cost - A Case Study in Linear Programming
Minimum ratio canceling is oracle polynomial for linear programming, but not strongly polynomial, even for networks
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, January 7-9, 2001, Washington, DC, USA
Universal Computation with Arbitrary Polyomino Tiles in Non-Cooperative Self-Assembly
Minimizing Convex Functions with Integral Minimizers
Concentration bounds for almost k -wise independence with applications to non-uniform security
Independent Set in P 5 -Free Graphs in Polynomial Time
Consensus of Interacting Particle Systems on Erdös-Rényi Graphs
Wavelet Trees Meet Suffix Trees
Fast approximation of centrality
Fully Dynamic Matching: -Approximation in Polylog Update Time
Near-Linear Time Approximation Schemes for some Implicit Fractional Packing Problems
Collision Detection in Aspect and Scale Bounded Polyhedra
Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution
Speeding Up Random Walks with Neighborhood Exploration
The Andoni-Krauthgamer-Razenshteyn characterization of sketchable norms fails for sketchable metrics
Fully polynomial-time parameterized computations for graphs and matrices of low treewidth
Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemerédi Graphs
Straight-skeleton based contour interpolation
Caching in networks (extended abstract)
Competitive analysis of organization networks or multicast acknowledgement: how much to wait?
Randomization does not help searching predecessors
Approximate Nearest Neighbor Search for Low Dimensional Queries
Fast and Memory-Efficient Algorithms for Evacuation Problems
Multidimensional matching and fast search in suffix trees
Generating random graphs with large girth
Network failure detection and graph connectivity
Digraph measures: Kelly decompositions, games, and orderings
On semidefinite programming relaxations for graph coloring and vertex cover
A Near-Quadratic Lower Bound for the Size of Quantum Circuits of Constant Treewidth
Clique-width: on the price of generality
Approximating Low-Stretch Spanners
Fixed-Parameter Tractability of Maximum Colored Path and Beyond
Minimizing Completion Times for Stochastic Jobs via Batched Free Times
Online Contention Resolution Schemes
The cover time of two classes of random graphs
Exponential bounds for DPLL below the satisfiability threshold
Top- k Document Retrieval in Compressed Space
An Optimal RAM Implementation of Catenable Min Double-ended Queues
Faster sublinear approximation of the number of k -cliques in low-arboricity graphs
Tight Bounds for Rumor Spreading with Vertex Expansion
Improved Roundtrip Spanners, Emulators, and Directed Girth Approximation
Prophet Secretary and Matching: the Significance of the Largest Item
A Nearly Tight Analysis of Greedy k-means++
Experimental analysis of simple, distributed vertex coloring algorithms
On the Change-Making Problem
The Local Lemma is Tight for SAT
The set of solutions of random XORSAT formulae
Computational advertising
Limits of Preprocessing for Single-Server PIR
On the competitive ratio of evaluating priced functions
Towards Multi-Pass Streaming Lower Bounds for Optimal Approximation of Max-Cut
Parameterized Complexity and Approximability of Directed Odd Cycle Transversal
Randomized Splay Trees
Checking Priority Queues
Small But Unwieldy: A Lower Bound on Adjacency Labels for Small Classes
An Unconditional Lower Bound for Two-Pass Streaming Algorithms for Maximum Matching Approximation
Graph algorithms for biological systems analysis
Adaptive Heuristics for Binary Search Trees and Constant Linkage Cost
Empirical Investigation of the Markov Reference Model
Sequential Random Permutation, List Contraction and Tree Contraction are Highly Parallel
A near-linear time algorithm for constructing a cactus representation of minimum cuts
The pure literal rule threshold and cores in random hypergraphs
A new approach to proving upper bounds for MAX-2-SAT
On the separation and equivalence of paging strategies
(Incremental) priority algorithms
Efficient Algorithms for Generalized Cut Trees
A Polynomial Time Algorithm for Finding a Minimum 4-Partition of a Submodular Function
Minimum Cuts and Shortest Non-Separating Cycles via Homology Covers
A simple storage scheme for strings achieving entropy bounds
A (3 + ɛ)-approximation algorithm for the minimum sum of radii problem with outliers and extensions for generalized lower bounds
Layout area of the hypercube (extended abstract)
Faster Algorithms for Bounded Knapsack and Bounded Subset Sum Via Fine-Grained Proximity Results
The maximum size of a Sidon set contained in a sparse random set of integers
Spencer's theorem in nearly input-sparsity time
Shortest paths in directed planar graphs with negative lengths: a linear-space O ( n log 2 n )-time algorithm
High rate fingerprinting codes and the fingerprinting capacity
A new approach to the orientation of random hypergraphs
On the Approximability of Budget Feasible Mechanisms
Dynamic Expression Trees and their Applications (Extended Abstract)
Determining the Evolutionary Tree
On the Competition Complexity of Dynamic Mechanism Design
Partial Coloring Complex, Vertex Decomposability and Tverberg's Theorem with Constraints
Reconstructing the Evolutionary History of Natural Languages
Fair allocation of a multiset of indivisible items
Algorithms for optimizing production DNA sequencing
Submodular functions are noise stable
Local Flow Partitioning for Faster Edge Connectivity
Approximating Weighted Tree Augmentation via Chvátal-Gomory Cuts
Emulations Between QSM, BSP, and LogP: A Framework for General-Purpose Parallel Algorithm Design
Towards a Calculus for Non-Linear Spectral Gaps
Strong recovery of geometric planted matchings
The space complexity of pass-efficient algorithms for clustering
Hermitian Diagonalization in Linear Precision
Approximation Schemes for Clustering with Outliers
Faster Agreement via a Spectral Method for Detecting Malicious Behavior
On the Locality of Hall's Theorem
Roundtrip spanners and roundtrip routing in directed graphs
On contract-and-refine transformations between phylogenetic trees
Viewing the Rings of a Tree: Minimum Distortion Embeddings into Trees
Local Distribution and the Symmetry Gap: Approximability of Multiway Partitioning Problems
On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique
Multiple choice tries and distributed hash tables
A note on the ring loading problem
Reachability Preservers: New Extremal Bounds and Approximation Algorithms
Counting good truth assignments of random k -SAT formulae
Deciding Contractibility of a Non-Simple Curve on the Boundary of a 3-Manifold
Approximate Euclidean shortest paths amid convex obstacles
Empty-ellipse graphs
Complexity of Delaunay triangulation for points on lower-dimensional polyhedra
A Tight Analysis of Slim Heaps and Smooth Heaps
An Optimal Lower Bound for Distinct Elements in the Message Passing Model
A Two-Pass (Conditional) Lower Bound for Semi-Streaming Maximum Matching
Fully Persistent Lists with Catenation
Streaming and Communication Complexity of Load-Balancing via Matching Contractors
More Asymmetry Yields Faster Matrix Multiplication
Large induced subgraphs via triangulations and CMSO
Robust positioning patterns
Improved algorithms for stretch scheduling
Weak duality for packing edge-disjoint odd ( u, v )-trails
Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 25-27 January 1998, San Francisco, California, USA
Truly Low-Space Element Distinctness and Subset Sum via Pseudorandom Hash Functions
Stop Minding Your p's and q's: A Simplified O ( n ) Planar Embedding Algorithm
Generalized Machine Activation Problems
Fully-Functional Succinct Trees
Circular Hulls and Orbiforms of Simple Polygons
Popular Matchings and Limits to Tractability
An Axiomatic and an Average-Case Analysis of Algorithms and Heuristics for Metric Properties of Graphs
Fast Fourier Sparsity Testing
The Demand Query Model for Bipartite Matching
Robust 1-bit Compressed Sensing with Iterative Hard Thresholding
The Combinatorics of the Longest-Chain Rule: Linear Consistency for Proof-of-Stake Blockchains
Efficient Algorithms for Constructing Very Sparse Spanners and Emulators
Spanners in Planar Domains via Steiner Spanners and non-Steiner Tree Covers
Simple and practical algorithm for sparse Fourier transform
Shrinking Lattice Polyhedra
An efficient sparse regularity concept
Nearly optimal computations with structured matrices
On the capacity of information networks
Lipschitz Continuous Algorithms for Covering Problems
A group-strategyproof mechanism for Steiner forests
Computing homotopic shortest paths in the plane
Convergence to approximate Nash equilibria in congestion games
One-Counter Markov Decision Processes
Augmenting Undirected Edge Connectivity in Õ(n 2 ) Time
Sorting Short Keys in Circuits of Size o ( n log n )
Counting Thin Subgraphs via Packings Faster Than Meet-in-the-Middle Time
Online point location in planar arrangements and its applications
Totally odd subdivisions and parity subdivisions: Structures and Coloring
On rectangle packing: maximizing benefits
Shortest Path in Complete Bipartite Digraph Problem and its Applications
A Faster Algorithm for Quickest Transshipments via an Extended Discrete Newton Method
When indexing equals compression: experiments with compressing suffix arrays and applications
On the Complexity of Information Spreading in Dynamic Networks
Cache-Oblivious Dynamic Dictionaries with Update/Query Tradeoffs
Fast Distributed Algorithms for {Brooks-Vizing} Colourings
A Lower Bound for Dynamic Fractional Cascading
Improved Steiner tree approximation in graphs
Exploring an Infinite Space with Finite Memory Scouts
Sample Efficient Toeplitz Covariance Estimation
Unlinking, splitting, and some other NP-hard problems in knot theory
Parallel algorithms and concentration bounds for the Lovász Local Lemma via witness-DAGs
Parameterized Approximation Scheme for Biclique-free Max k -Weight SAT and Max Coverage
On the connectivity of dynamic random geometric graphs
Self-Testing Polynomial Functions Efficiently and Over Rational Domains
On the number of matroids
Sparsity and dimension
Fast Convergence of Fictitious Play for Diagonal Payoff Matrices
Selfish routing with atomic players
Ramsey Spanning Trees and their Applications
A Little Charity Guarantees Almost Envy-Freeness
Bucket Oblivious Sort: An Extremely Simple Oblivious Sort
Asymmetric Convex Intersection Testing
An O(n 2 ) Time Algorithm for the 2-Chain Cover Problem and Related Problems
Robust randomized matchings
Balanced Allocations with Heterogeneous Bins: The Power of Memory
Vertex Sparsification for Edge Connectivity
Multiway Simple Cycle Separators and I/O-Efficient Algorithms for Planar Graphs
Möbius-invariant natural neighbor interpolation
New Additive Spanners
Fully-Dynamic All-Pairs Shortest Paths: Improved Worst-Case Time and Space Bounds
Losing Treewidth by Separating Subsets
To Augment or Not to Augment: Solving Unsplittable Flow on a Path by Creating Slack
On the number of crossing-free matchings, (cycles, and partitions)
Online Mixed Packing and Covering
Low Congestion Cycle Covers and Their Applications
An efficient cost-sharing mechanism for the prize-collecting Steiner forest problem
Delayed Path Coupling and Generating Random Permutations via Distributed Stochastic Processes
Improved approximation algorithms for rectangle tiling and packing
O (depth)-Competitive Algorithm for Online Multi-level Aggregation
An approximation algorithm for cutting out convex polygons
Pricing Randomized Allocations
Improved Dual Network Simplex
The Suffix of a Square Matrix, with Applications
Randomized Robot Navigation Algorithms
Is the internet fractal?
Communication Complexity of Permutation-Invariant Functions
DAG-width: connectivity measure for directed graphs
Minimizing maximum response time in scheduling broadcasts
The Knuth-Yao quadrangle-inequality speedup is a consequence of total-monotonicity
Exponential Lower Bounds for the PPSZ k -SAT Algorithm
Relative Error Tensor Low Rank Approximation
Strong price of anarchy
Offline Maintenance of Planar Configurations
A Uniform Framework for Approximating Weighted Connectivity Problems
Integrality ratio for group Steiner trees and directed steiner trees
Impossibility of dimension reduction in the nuclear norm
Black-box reductions for cost-sharing mechanism design
Dynamic TCP acknowledgement: penalizing long delays
Shorter Labeling Schemes for Planar Graphs
Equivalences between triangle and range query problems
Computing a Face in an Arrangement of Line Segments
The similarity metric
How to Sell Hyperedges: The Hypermatching Assignment Problem
Adversarial models in evolutionary game dynamics
A Short Proof of the Toughness of Delaunay Triangulations
An O(log* n) Approximation Algorithm for the Asymmetric p-Center Problem
A Practical Approximation Algorithm for the LMS Line Estimator
Fully Dynamic Approximate Minimum Cut in Subpolynomial Time per Operation
Faster quantum algorithm for evaluating game trees
Approximation algorithms for cycle packing problems
Timing in chemical reaction networks
Perfect Matchings, Rank of Connection Tensors and Graph Homomorphisms
Analysis of Practical Backoff Protocols for Contention Resolution with Multiple Servers
An almost 2-approximation for all-pairs of shortest paths in subquadratic time
A fast approximation scheme for fractional covering problems with variable upper bounds
A faster distributed protocol for constructing a minimum spanning tree
Cheeger Inequalities for Submodular Transformations
Discrete Convexity and Polynomial Solvability in Minimum 0-Extension Problems
Hopcroft's Problem, Log-Star Shaving, 2D Fractional Cascading, and Decision Trees
On Succinct Convex Greedy Drawing of 3-Connected Plane Graphs
Improved Region-Growing and Combinatorial Algorithms for k -Route Cut Problems (Extended Abstract)
On finding a guard that sees most and a shop that sells most
Algorithms for Persuasion with Limited Communication
Relating singular values and discrepancy of weighted directed graphs
A simple and fast 2-approximation algorithms for the one-warehouse multi-retailers problem
FPTAS for mixed-integer polynomial optimization with a fixed number of variables
On approximating strip packing with a better ratio than 3/2
Improved Pattern-Avoidance Bounds for Greedy BSTs via Matrix Decomposition
An Optimal-Time Construction of Sparse Euclidean Spanners with Tiny Diameter
Optimal approximation for submodular and supermodular optimization with bounded curvature
Improving the Leading Constant of Matrix Multiplication
Distributions of points in the unit-square and large k -gons
String hashing for linear probing
Top-K Color Queries for Document Retrieval
The independent even factor problem
Anaconda: A Non-Adaptive Conditional Sampling Algorithm for Distribution Testing
Weighted Completion Time Minimization for Unrelated Machines via Iterative Fair Contention Resolution
Packing multiway cuts in capacitated graphs
An Analysis of the Burrows-Wheeler Transform
Towards computing the Grothendieck constant
An Optimal Algorithm for the Maximum Two-Chain Problem
Decremental Dynamic Connectivity
A Sublinear Bound on the Page Number of Upward Planar Graphs
Incidences with curves and surfaces in three dimensions, with applications to distinct and repeated distances
Polygonal path approximation with angle constraints
Triangulations Admit Dominating Sets of Size 2 n /7
Hypercontractive inequalities via SOS, and the Frankl-Rödl graph
Incentive compatible regression learning
Lopsidependency in the Moser-Tardos framework: Beyond the Lopsided Lovász Local Lemma
Efficient algorithms for maximum weight matchings in general graphs with small edge weights
Facility location with hierarchical facility costs
Adaptive set intersections, unions, and differences
Optimizing the sum of linear fractional functions and applications
Recognizing partial cubes in quadratic time
Hamiltonicity of random subgraphs of the hypercube
A Unified Framework for Clustering Constrained Data without Locality Property
A Nearly-Tight Analysis of Multipass Pairing Heaps
Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints
Lower Bounds for Oblivious Near-Neighbor Search
A Note on Iterated Rounding for the Survivable Network Design Problem
Constructing worst case instances for semidefinite programming based approximation algorithms
Slice and dice: a simple, improved approximate tiling recipe
An optimal (expected time) algorithm for minimizing lab costs in DNA sequencing
Fully-Distributed Byzantine Agreement in Sparse Networks
Neighborhood Preserving Hashing and Approximate Queries
Prophet Secretary for Combinatorial Auctions and Matroids
Bounding ε -scatter dimension via metric sparsity
Exact Community Recovery in the Geometric SBM
Absolute convergence: true trees from short sequences
Erratum: an approximation algorithm for minimum-cost vertex-connectivity problems
Fast concurrent access to parallel disks
Deterministic Algorithms for Submodular Maximization Problems
Unknotting is in AM cup co-AM
Augmenting Edge Connectivity via Isolating Cuts
Revenue maximization when bidders have budgets
FPTAS for Counting Monotone CNF
Fast Backtracking Principles Applied to Find New Cages
Random MAX SAT, random MAX CUT, and their phase transitions
Characterizations of k-Terminal Flow Networks and Computing Network Flows in Partial k-Trees
An improved approximation algorithm for the partial latin square extension problem
Fully Polynomial-Time Approximation Schemes for Fair Rent Division
On Indexing and Compressing Finite Automata
Finding one tight cycle
On Approximating (Sparse) Covering Integer Programs
Exploring Unknown Environments with Obstacles
Inserting an edge into a planar graph
Randomized Shellsort: A Simple Oblivious Sorting Algorithm
The Power of Distributed Verifiers in Interactive Proofs
Uniform generation of random graphs with power-law degree sequences
An Effective Additive Basis for the Integers
On the Exact Worst Case Query Complexity of Planar Point Location
Efficient Algorithms for Robustness in Matroid Optimization
An Alon-Boppana Type Bound for Weighted Graphs and Lowerbounds for Spectral Sparsification
Annotations for Sparse Data Streams
Stability of Networks and Protocols in the Adversarial Queueing Model for Packet Routing
On universally easy classes for NP-complete problems
Better Approximation Bounds for the Joint Replenishment Problem
Fully Dynamic Exact Edge Connectivity in Sublinear Time
Perfect Matching in Random Graphs is as Hard as Tseitin
Approximating Maximin Share Allocations
The Communication Complexity of Optimization
Two-phase greedy algorithms for some classes of combinatorial linear programs
The Minority Dynamics and the Power of Synchronicity
An 8/13-approximation algorithm for the asymmetric maximum TSP
On (1 + ɛ)-Approximate Flow Sparsifiers
Dominator tree verification and vertex-disjoint paths
Oblivious network design
A Polynomial-Time Algorithm for 1/2-Well-Supported Nash Equilibria in Bimatrix Games
Fréchet Distance in Subquadratic Time
Connectivity Labeling Schemes for Edge and Vertex Faults via Expander Hierarchies
Generating random factored numbers, easily
Linear Size Distance Preservers
A deterministic algorithm for the cost-distance problem
Scheduling techniques for media-on-demand
Fast load balancing via bounded best response
A New Approach to Estimating Effective Resistances and Counting Spanning Trees in Expander Graphs
Fast LP-based Approximations for Geometric Packing and Covering Problems
Triply efficient shadow tomography
Improved Bicriteria Existence Theorems for Scheduling
Dimension-Preserving Reductions Between SVP and CVP in Different p -Norms
On stars and Steiner stars: II
A constant factor approximation algorithm for k -median clustering with outliers
Exact computation of a manifold metric, via Lipschitz Embeddings and Shortest Paths on a Graph
A spectral heuristic for bisecting random graphs
Reachability and distance queries via 2-hop labels
Code Sparsification and its Applications