Karol Wkegrzycki

collaborators

3 papers

cs.FL2025

Fine-Grained Complexity of Ambiguity Problems on Automata and Directed Graphs

Karolina Drabik, Anita DÃ¼rr, Fabian Frei +2

In the field of computational logic, two classes of finite automata are considered fundamental: deterministic and nondeterministic automata (DFAs and NFAs). In a more fine-grained…

cs.DS2024

Space-Efficient Algorithm for Integer Programming with Few Constraints

Lars Rohwedder, Karol WÄgrzycki

Integer linear programs $min {c^{T} x : A x = b, x \in Z_{\geq 0}^{n}}$ , where $A \in Z^{m \times n}$ , $b \in Z^{m}$ , and $c \in Z^{n}$ , can be solved…

cs.DS2024

Fine-Grained Equivalence for Problems Related to Integer Linear Programming

Lars Rohwedder, Karol WÄgrzycki

Integer Linear Programming with $n$ binary variables and $m$ many $0/1$ -constraints can be solved in time $2^{O ~ (m^{2})} poly (n)$ and it is open whether the dependence o…