[Untitled]

Autor: Raphaël Clifford, Markus Jalsenius, Benjamin Sach

Publikováno v: Theory of Computing. 15:1-31

We give tight cell-probe bounds for the time to compute convolution, multiplication and Hamming distance in a stream. The cell probe model is a particularly strong computational model and subsumes, for example, the popular word RAM model. • We firs

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::cf21257c5f03921f1f2ebd46b8fc95e3
https://doi.org/10.4086/toc.2019.v015a002

The complexity of weighted Boolean #CSP with mixed signs

Autor: Leslie Ann Goldberg, Andrei A. Bulatov, David Richerby, Martin Dyer, Markus Jalsenius

Publikováno v: Theoretical Computer Science. 410(38-40):3949-3961

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 functi

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::365f3c073e3dcd5c4af69e0a3e8af9e0

Improved Mixing Bounds for the Anti-Ferromagnetic Potts Model on Z2

Autor: Markus Jalsenius, Russell Martin, Mike Paterson, Leslie Ann Goldberg

Publikováno v: LMS Journal of Computation and Mathematics. 9:1-20

The authors of this paper consider the anti-ferromagnetic Potts model on the the integer lattice Z2. The model has two parameters: q, the number of spins, and λ = exp(−β), where β 4 is ‘inverse temperature’. It is known that the model has st

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::21864df33e28494bf1df68c8ef16b92c
https://doi.org/10.1112/s1461157000001169

Space Lower Bounds for Online Pattern Matching

Autor: Ely Porat, Markus Jalsenius, Benjamin Sach, Raphaël Clifford

Publikováno v: Combinatorial Pattern Matching ISBN: 9783642214578
CPM

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 betwee

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::922b0cd08d535828d8a8f34774e2f823
https://doi.org/10.1007/978-3-642-21458-5_17

Pattern Matching under Polynomial Transformation

Autor: Ayelet Butman, Benny Porat, Peter Clifford, Benjamin Sach, Raphaël Clifford, Ely Porat, Markus Jalsenius, Noa Lewenstein

Publikováno v: Butman, A, Peter, C, Clifford, R, Jalsenius, M T, Lewenstein, N, Porat, B & Porat, E 2013, ' Pattern matching under polynomial transformation ', SIAM Journal on Computing, vol. 42, no. 2, pp. 611-633 . https://doi.org/10.1137/110853327

We consider a class of pattern matching problems where a normalising transformation is applied at every alignment. Normalised pattern matching plays a key role in fields as diverse as image processing and musical information processing where applicat

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::14a560671d01392fe5c519cc1a9ee65c