17 citations · 22 across the 5 of their papers we have counts for
8 papers
The -binding function of -directional segment graphs
Lech Duraj, Ross J. Kang, Hoang La +4
Given a positive integer , the class -DIR is defined as all those intersection graphs formed from a finite collection of line segments in having at most s…
Better Diameter Algorithms for Bounded VC-dimension Graphs and Geometric Intersection Graphs
Lech Duraj, Filip Konieczny, Krzysztof Potępa
We develop a framework for algorithms finding the diameter in graphs of bounded distance Vapnik-Chervonenkis dimension, in (parameterized) subquadratic time complexity. The class o…
Random hypergraphs and property B
Lech Duraj, Jakub Kozik, Dmitry Shabanov
In 1964 Erdős proved that $(1+\oh{1})) \frac{\eul \ln(2)}{4} k^2 2^{k}$ edges are sufficient to build a -graph which is not two colorable. To this day, it is not known whether t…
Equivalences between triangle and range query problems
Lech Duraj, Krzysztof Kleiner, Adam Polak +1
We define a natural class of range query problems, and prove that all problems within this class have the same time complexity (up to polylogarithmic factors). The equivalence is v…
A sub-quadratic algorithm for the longest common increasing subsequence problem
Lech Duraj
The Longest Common Increasing Subsequence problem (LCIS) is a natural variant of the celebrated Longest Common Subsequence (LCS) problem. For LCIS, as well as for LCS, there is an…
A note on two-colorability of nonuniform hypergraphs
Lech Duraj, Grzegorz Gutowski, Jakub Kozik
For a hypergraph , let denote the expected number of monochromatic edges when the color of each vertex in is sampled uniformly at random from the set of size 2. Let $…
Tight Conditional Lower Bounds for Longest Common Increasing Subsequence
Lech Duraj, Marvin Künnemann, Adam Polak
We consider the canonical generalization of the well-studied Longest Increasing Subsequence problem to multiple sequences, called -LCIS: Given integer sequences $X_1,\dots,X…
Chip games and paintability
Lech Duraj, Grzegorz Gutowski, Jakub Kozik
We prove that the difference between the paint number and the choice number of a complete bipartite graph is . That answers the question of Zhu (2009) wh…