92 citations · 156 across the 18 of their papers we have counts for
3 papers · 1 filter
Separating OR, SUM, and XOR Circuits
Magnus Find, Mika Göös, Matti Järvisalo +3
Given a boolean n by n matrix A we consider arithmetic circuits for computing the transformation x->Ax over different semirings. Namely, we study three circuit models: monotone OR-…
On the parameterized complexity of cutting a few vertices from a graph
Fedor V. Fomin, Petr A. Golovach, Janne H. Korhonen
We study the parameterized complexity of separating a small set of vertices from a graph by a small vertex-separator. That is, given a graph and integers , , the task is…
Synchronous Counting and Computational Algorithm Design
Danny Dolev, Keijo Heljanko, Matti Järvisalo +5
Consider a complete communication network on nodes, each of which is a state machine. In synchronous 2-counting, the nodes receive a common clock pulse and they have to agree o…