Adam Polak

activity

20152026

most citedCounting Triangles in Large Graphs on GPU

45 citations · 92 across the 19 of their papers we have counts for

collaborators

Showing 2017Show all

3 papers · 1 filter

cs.CC2017

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 $k$ -LCIS: Given $k$ integer sequences $X_1,\dots,X…

math.CO2017★ 4 cited

On an extremal problem for poset dimension

Grzegorz Guśpiel, Piotr Micek, Adam Polak

Let $f (n)$ be the largest integer such that every poset on $n$ elements has a $2$ -dimensional subposet on $f (n)$ elements. What is the asymptotics of $f (n)$ ? It is easy to see that…

cs.CC2017★ 7 cited

Why is it hard to beat $O (n^{2})$ for Longest Common Weakly Increasing Subsequence?

Adam Polak

The Longest Common Weakly Increasing Subsequence problem (LCWIS) is a variant of the classic Longest Common Subsequence problem (LCS). Both problems can be solved with simple quadr…

Tight Conditional Lower Bounds for Longest Common Increasing Subsequence

On an extremal problem for poset dimension

Why is it hard to beat O(n2) for Longest Common Weakly Increasing Subsequence?

Why is it hard to beat $O (n^{2})$ for Longest Common Weakly Increasing Subsequence?