László Kozma :: Research


Research interests

Fundamental data structures and algorithms, combinatorics (permutations, graphs, set systems), computational geometry, machine learning.

Publications

  • Improved bounds for multipass pairing heaps and path-balanced binary search trees
    with Dani Dorfman, Haim Kaplan, Seth Pettie, Uri Zwick, In submission.
    [pdf-soon]

  • Summary: We improve the analysis of a classical pairing heap variant (Fredman, Sedgewick, Sleator, Tarjan, 1985) and a classical self-adjusting binary search tree heuristic (Sleator, 198x) from roughly O(logn loglog n) to better than O(logn log^(k) n) for any constant k, getting closer to the conjectured O(log n). (Here, log^(k) means log(.) iterated k times.)

  • Time- and space-optimal algorithm for the many-visits TSP
    with André Berger, Matthias Mnich, Roland Vincze, In submission.
    [pdf] [update-soon]

  • Summary: In the many-visits TSP, a salesperson must visit n cities, each of them precisely a prescribed number of times (in the cheapest possible way). We give a polynomial-space algorithm for this problem, with running time that depends single-exponentially on the number of cities and logarithmically on the total number of visits in the tour. This improves on the previous best algorithm by Papadimitriou and Cosmadakis from 1984, that has superexponential time- and space-complexity.

  • Selection from heaps, row-sorted matrices and X + Y using soft heaps
    with Haim Kaplan, Or Zamir, Uri Zwick, In submission.
    [pdf] [slides-soon]

  • Summary: Using soft heaps, we obtain simpler optimal algorithms for selecting the k-th smallest item from heap-ordered trees, from sets of sorted lists, and from sets of pairwise sums (X + Y), matching, and in some ways extending classical results of Frederickson (1993) and Frederickson and Johnson (1982).

  • Smooth heaps and a dual view of self-adjusting data structures
    with Thatchaphol Saranurak, STOC 2018.
    (Invited to SICOMP special issue for STOC.)
    [pdf]

  • Summary: We describe a new connection ("duality") between self-adjusting binary search trees (BSTs) and heaps. This allows us to transfer results between the two settings, obtaining: (1) a broad class of "stable" heap algorithms, (2) instance-specific lower and upper bounds for stable heaps, (3) a new heap data structure called "smooth heap", which we show to be the heap-counterpart of a BST that is conjectured to be "instance-optimal".

  • Multi-finger binary search trees
    with Parinya Chalermsook, Mayank Goswami, Kurt Mehlhorn, Thatchaphol Saranurak, In submission.
    [pdf-soon]

  • Summary: We show that Binary Search Trees (BSTs) with multiple fingers can be efficiently simulated by standard (one-finger) BSTs. The results connect two prominent online problems: dynamic BSTs and k-server. As an application we show that BSTs are efficient when accessing items close to some recently accessed item.

    The paper builds upon (and partially supersedes) the technical report The landscape of bounds for binary search trees. [pdf]
    Results found only in the report: a survey of BST properties; new connections/separations between BST properties; a new, more intuitive analysis of Splay trees; a technique for composing ("interleaving") sequences and combining BST properties; an observation about the Move-to-root heuristic.

  • Pairing heaps: the forward variant
    with Dani Dorfman, Haim Kaplan, Uri Zwick, In submission.
    [pdf]

  • Summary: We improve the analysis of a classical pairing heap variant (Fredman, Sedgewick, Sleator, Tarjan, 1985) from O(n^0.5) to better than O(n^eps) for any constant eps>0.

  • Maximum Scatter TSP in Doubling Metrics
    with Tobias Mömke, SODA 2017.
    [pdf] [slides]

    Supersedes preliminary paper presented at EuroCG 2016. [pdf]

  • Summary: We give a polynomial time (1+eps)-approximation for euclidean (and more general) cases of the Traveling-Salesman variant in which no hop may be too short, improving on the earlier best ratio of 2.

  • Binary search trees, rectangles and patterns, PhD thesis, Saarland University, 2016.
    [pdf] [slides]

  • Summary: Contains results related to binary search trees and the dynamic optimality conjecture from three separate papers, expanded, and with an additional broad survey of the problem, as well as some new observations.

  • Binary search trees and rectangulations
    with Thatchaphol Saranurak, Manuscript, 2016.
    [pdf]

  • Summary: Serving a sequence of searches in a binary search tree with rotations is shown to be equivalent with the problem of finding a sequence of flips between two rectangulations.

  • Hitting Set for hypergraphs of low VC-dimension
    with Karl Bringmann, Shay Moran, N.S. Narayanaswamy, ESA 2016.
    [pdf]

  • Summary: The Hitting Set problem remains hard (in the parameterized sense), even in set systems of very small VC-dimension. If we restrict the structure even more, then Hitting Set is solvable in polynomial time. Our easy class is a generalization of Edge Cover.

  • Pattern-avoiding access in binary search trees
    with Parinya Chalermsook, Mayank Goswami, Kurt Mehlhorn, Thatchaphol Saranurak, FOCS 2015, HALG 2016.
    [pdf] [slides I - Thatchaphol] [slides II]

  • Summary: Searches in binary search trees (BSTs) take almost constant (amortized) time if the search sequence avoids an arbitrary fixed pattern. Moreover, this is attained by Greedy, a general-purpose BST algorithm that is conjectured optimal (for every sequence). Pattern avoiding sequences generalize some well-studied earlier examples, which can be seen as avoiding some particular pattern. Some of the arguments rely on results from forbidden submatrix theory.

  • Greedy Is an Almost Optimal Deque
    with Parinya Chalermsook, Mayank Goswami, Kurt Mehlhorn, Thatchaphol Saranurak, WADS 2015.
    [pdf] [slides - Thatchaphol]

  • Summary: We extend the "geometry of BST" model of Demaine et al. to handle insert and delete operations, and we show that the Greedy algorithm is almost optimal on deque sequences (where insert and delete happens only at the minimum and maximum). The results give evidence that Greedy may be instance-optimal.

  • Self-Adjusting Binary Search Trees: What Makes Them Tick?
    with Parinya Chalermsook, Mayank Goswami, Kurt Mehlhorn, Thatchaphol Saranurak, ESA 2015.
    [pdf] [slides]

  • Summary: We give combinatorial conditions that guarantee the efficiency of self-adjusting binary search tree algorithms, unifying the analysis of several known heuristics, and obtaining new, efficient heuristics based on depth-reduction. We also characterize all heuristics that are local. The paper supersedes an earlier draft note [pdf] which may nonetheless contain additional intuition.

  • Streaming Algorithms for Partitioning Integer Sequences
    with Christian Konrad, Manuscript, 2014.
    [pdf]

  • Summary: We study the problem of partitioning a stream of integers into blocks with roughly equal total value, in one pass. We look at the trade-off between approximation-ratio and amount of memory used.

  • Shattering, Graph Orientations, and Connectivity
    with Shay Moran, Electronic Journal of Combinatorics, Vol 20(3), 2013.
    [pdf] [slides]

  • Summary: We interpret results for set systems, shattering, and VC-dimension, in the context of graph orientations. We thus obtain a number of inequalities (some known, some new) involving distances, flows, connectivity, forbidden subgraphs, etc., in graphs. A warm-up example: the number of orientations of a graph G in which there is an s-to-t directed path equals the number of spanning subgraphs of G in which s and t are connected, for every G, s, t.

  • Privacy by Fake Data: A Geometric Approach
    with Victor Alvarez, Erin Chambers, CCCG 2013.
    [pdf]

  • Summary: Given n points in d dimensions, add as few extra points as possible, such that no point can be isolated within a unit box. The problem arises in the context of data privacy. We give approximation and hardness results.

  • Minimum Average Distance Triangulations
    ESA 2012.
    [pdf] [slides] [poster]

  • Summary: How to connect n points in the plane with a non-crossing network, such that the average distance between a pair of points is as small as possible. In general, the problem is shown to be hard, in the unit-weight case a non-trivial polynomial-time algorithm is found, and the metric/euclidean case is left open.

  • Binary Principal Component Analysis in the Netflix Collaborative Filtering Task
    with Alexander Ilin, Tapani Raiko, MLSP 2009.
    [pdf] [slides]

  • Summary: We propose a PCA-like factorization algorithm for binary matrices with missing values, that scales well to very high dimensional and very sparse data. Together with a binarization method, the algorithm directly reconstructs integer entries within a small range, it is thus well-suited for predicting ratings in collaborative filtering.

[DBLP | Google Scholar]

Misc.



To my home page.