3 papers
math.CO2021
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…
cs.CC2019
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…
cs.DS2019
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…