research
∙
08/17/2022
Constant-Depth Sorting Networks
In this paper, we address sorting networks that are constructed from com...
share
research
∙
07/19/2022
Polynomial Threshold Functions for Decision Lists
For S ⊆{0,1}^n a Boolean function f S →{-1,1} is a polynomial threshold...
research
∙
08/01/2021
Deciding boundedness of monadic sirups
We show that deciding boundedness (aka FO-rewritability) of monadic sing...
research
∙
06/07/2020
A data complexity and rewritability tetrachotomy of ontology-mediated queries with a covering axiom
Aiming to understand the data complexity of answering conjunctive querie...
research
∙
02/18/2020
Multiparty Karchmer-Wigderson Games and Threshold Circuits
We suggest a generalization of Karchmer-Wigderson communication games to...
research
∙
12/31/2018
Complexity of Linear Operators
Let A ∈{0,1}^n × n be a matrix with z zeroes and u ones and x be an n-di...
research
∙
06/11/2014
