Markus Jalsenius

SODA Conference 2015 Conference Paper

Cell-probe bounds for online edit distance and other pattern matching problems

• Raphaël Clifford
• Markus Jalsenius
• Benjamin Sach

TCS Journal 2013 Journal Article

Space lower bounds for online pattern matching

• Raphaël Clifford
• Markus Jalsenius
• Ely Porat
• Benjamin Sach

We present space lower bounds for online pattern matching under a number of different distance measures. Given a pattern of length m and a text that arrives one character at a time, the online pattern matching problem is to report the distance between the pattern and a sliding window of the text as soon as the new character arrives. We require that the correct answer is given at each position with constant probability. We give Ω ( m ) bit space lower bounds for L 1, L 2, L ∞, Hamming, edit and swap distances as well as for any algorithm that computes the cross-correlation/convolution. We then show a dichotomy between distance functions that have wildcard-like properties and those that do not. In the former case which includes, as an example, pattern matching with character classes, we give Ω ( m ) bit space lower bounds. For other distance functions, we show that there exist space bounds of Ω ( log m ) and O ( log 2 m ) bits. Finally we discuss space lower bounds for non-binary inputs and show how in some cases they can be improved.

SODA Conference 2013 Conference Paper

Tight Cell-Probe Bounds for Online Hamming Distance Computation

• Raphaël Clifford
• Markus Jalsenius
• Benjamin Sach

We show tight bounds for online Hamming distance computation in the cell-probe model with word size w. The task is to output the Hamming distance between a fixed string of length n and the last n symbols of a stream. We give a lower bound of time on average per output, where δ is the number of bits needed to represent an input symbol. We argue that this bound is tight within the model. The lower bound holds under randomisation and amortisation.

TCS Journal 2009 Journal Article

The complexity of weighted Boolean #CSP with mixed signs

• Andrei Bulatov
• Martin Dyer
• Leslie Ann Goldberg
• Markus Jalsenius
• David Richerby

We give a complexity dichotomy for the problem of computing the partition function of a weighted Boolean constraint satisfaction problem. Such a problem is parameterized by a set Γ of rational-valued functions, which generalize constraints. Each function assigns a weight to every assignment to a set of Boolean variables. Our dichotomy extends previous work in which the weight functions were restricted to being non-negative. We represent a weight function as a product of the form ( − 1 ) s g, where the polynomial s determines the sign of the weight and the non-negative function g determines its magnitude. We show that the problem of computing the partition function (the sum of the weights of all possible variable assignments) is in polynomial time if either every function in Γ can be defined by a “pure affine” magnitude with a quadratic sign polynomial or every function can be defined by a magnitude of “product type” with a linear sign polynomial. In all other cases, computing the partition function is FP #P -complete.