research
∙
12/07/2022
Combinatorial generation via permutation languages. V. Acyclic orientations
In 1993, Savage, Squire, and West described an inductive construction fo...
share
research
∙
12/06/2022
Improved Algebraic Degeneracy Testing
In the classical linear degeneracy testing problem, we are given n real ...
research
∙
10/26/2022
Inapproximability of shortest paths on perfect matching polytopes
We consider the computational problem of finding short paths in the skel...
research
∙
09/15/2021
Subquadratic Algorithms for Some 3Sum-Hard Geometric Problems in the Algebraic Decision Tree Model
We present subquadratic algorithms in the algebraic decision-tree model ...
research
∙
08/18/2021
Worst-Case Efficient Dynamic Geometric Independent Set
We consider the problem of maintaining an approximate maximum independen...
research
∙
06/30/2021
Combinatorial generation via permutation languages. IV. Elimination trees
An elimination tree for a connected graph G is a rooted tree on the vert...
research
∙
06/30/2021
Bounds on the Diameter of Graph Associahedra
Graph associahedra are generalized permutohedra arising as special cases...
research
∙
06/28/2021
Dynamic Schnyder Woods
A realizer, commonly known as Schnyder woods, of a triangulation is a pa...
research
∙
06/24/2021
Approximability of (Simultaneous) Class Cover for Boxes
Bereg et al. (2012) introduced the Boxes Class Cover problem, which has ...
research
∙
06/10/2021
An Instance-optimal Algorithm for Bichromatic Rectangular Visibility
Afshani, Barbay and Chan (2017) introduced the notion of instance-optima...
research
∙
08/19/2020
Modular Subset Sum, Dynamic Strings, and Zero-Sum Sets
The modular subset sum problem consists of deciding, given a modulus m, ...
research
∙
07/16/2020
Dynamic Geometric Independent Set
We present fully dynamic approximation algorithms for the Maximum Indepe...
research
∙
03/26/2020
Geometric Pattern Matching Reduces to k-SUM
We prove that some exact geometric pattern matching problems reduce in l...
research
∙
02/13/2020
Drawing Graphs as Spanners
We study the problem of embedding graphs in the plane as good geometric ...
research
∙
01/22/2020
Chirotopes of Random Points in Space are Realizable on a Small Integer Grid
We prove that with high probability, a uniform sample of n points in a c...
research
∙
08/02/2019
Competitive Online Search Trees on Trees
We consider the design of adaptive data structures for searching element...
research
∙
08/01/2019
Sparse Regression via Range Counting
The sparse regression problem, also known as best subset selection probl...
research
∙
03/06/2019
Encoding 3SUM
We consider the following problem: given three sets of real numbers, out...
research
∙
02/18/2019
Information-theoretic lower bounds for quantum sorting
We analyze the quantum query complexity of sorting under partial informa...
research
∙
02/16/2019
Flip distances between graph orientations
Flip graphs are a ubiquitous class of graphs, which encode relations ind...
research
∙
06/26/2018
Finding a Maximum-Weight Convex Set in a Chordal Graph
We consider a natural combinatorial optimization problem on chordal grap...
research
∙
05/10/2018
Reconfiguration of Satisfying Assignments and Subset Sums: Easy to Find, Hard to Connect
We consider the computational complexity of reconfiguration problems, in...
research
∙
03/30/2018
On the Diameter of Tree Associahedra
We consider a natural notion of search trees on graphs, which we show is...
research
∙
01/05/2018
Subquadratic Encodings for Point Configurations
For most algorithms dealing with sets of points in the plane, the only r...
research
∙
12/21/2017
A Note on Flips in Diagonal Rectangulations
Rectangulations are partitions of a square into axis-aligned rectangles....
research
∙
08/21/2017
Helly Numbers of Polyominoes
We define the Helly number of a polyomino P as the smallest number h suc...
research
∙
02/28/2013