BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Markus Jalsenius

Markus Jalsenius contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Data Structures and AlgorithmsComputational ComplexityDiscrete Mathematicsmath-phmath.MP

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
10works
0followers
5topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

10 published item(s)

preprint2012arXiv

Parameterized Matching in the Streaming Model

We study the problem of parameterized matching in a stream where we want to output matches between a pattern of length m and the last m symbols of the stream before the next symbol arrives. Parameterized matching is a natural generalisation of exact matching where an arbitrary one-to-one relabelling of pattern symbols is allowed. We show how this problem can be solved in constant time per arriving stream symbol and sublinear, near optimal space with high probability. Our results are surprising and important: it has been shown that almost no streaming pattern matching problems can be solved (not even randomised) in less than Theta(m) space, with exact matching as the only known problem to have a sublinear, near optimal space solution. Here we demonstrate that a similar sublinear, near optimal space solution is achievable for an even more challenging problem. The proof is considerably more complex than that for exact matching.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Pattern Matching in Multiple Streams

We investigate the problem of deterministic pattern matching in multiple streams. In this model, one symbol arrives at a time and is associated with one of s streaming texts. The task at each time step is to report if there is a new match between a fixed pattern of length m and a newly updated stream. As is usual in the streaming context, the goal is to use as little space as possible while still reporting matches quickly. We give almost matching upper and lower space bounds for three distinct pattern matching problems. For exact matching we show that the problem can be solved in constant time per arriving symbol and O(m+s) words of space. For the k-mismatch and k-difference problems we give O(k) time solutions that require O(m+ks) words of space. In all three cases we also give space lower bounds which show our methods are optimal up to a single logarithmic factor. Finally we set out a number of open problems related to this new model for pattern matching.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Tight Cell-Probe Bounds for Online Hamming Distance Computation

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 Omega((d/w)*log n) time on average per output, where d 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.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Tight Cell-Probe Bounds for Online Integer Multiplication and Convolution

We show tight bounds for both online integer multiplication and convolution in the cell-probe model with word size w. For the multiplication problem, one pair of digits, each from one of two n digit numbers that are to be multiplied, is given as input at step i. The online algorithm outputs a single new digit from the product of the numbers before step i+1. We give a Theta((d/w)*log n) bound on average per output digit for this problem where 2^d is the maximum value of a digit. In the convolution problem, we are given a fixed vector V of length n and we consider a stream in which numbers arrive one at a time. We output the inner product of V and the vector that consists of the last n numbers of the stream. We show a Theta((d/w)*log n) bound for the number of probes required per new number in the stream. All the bounds presented hold under randomisation and amortisation. Multiplication and convolution are central problems in the study of algorithms which also have the widest range of practical applications.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Space Lower Bounds for Online Pattern Matching

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 Omega(m) bit space lower bounds for L_1, L_2, L_\infty, 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 Omega(m) bit space lower bounds. For other distance functions, we show that there exist space bounds of Omega(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.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

The Complexity of Approximating Bounded-Degree Boolean \sharp CSP

The degree of a CSP instance is the maximum number of times that any variable appears in the scopes of constraints. We consider the approximate counting problem for Boolean CSP with bounded-degree instances, for constraint languages containing the two unary constant relations {0} and {1}. When the maximum allowed degree is large enough (at least 6) we obtain a complete classification of the complexity of this problem. It is exactly solvable in polynomial-time if every relation in the constraint language is affine. It is equivalent to the problem of approximately counting independent sets in bipartite graphs if every relation can be expressed as conjunctions of {0}, {1} and binary implication. Otherwise, there is no FPRAS unless NP=RP. For lower degree bounds, additional cases arise, where the complexity is related to the complexity of approximately counting independent sets in hypergraphs.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

The Complexity of Flood Filling Games

We study the complexity of the popular one player combinatorial game known as Flood-It. In this game the player is given an n by n board of tiles where each tile is allocated one of c colours. The goal is to make the colours of all tiles equal via the shortest possible sequence of flooding operations. In the standard version, a flooding operation consists of the player choosing a colour k, which then changes the colour of all the tiles in the monochromatic region connected to the top left tile to k. After this operation has been performed, neighbouring regions which are already of the chosen colour k will then also become connected, thereby extending the monochromatic region of the board. We show that finding the minimum number of flooding operations is NP-hard for c>=3 and that this even holds when the player can perform flooding operations from any position on the board. However, we show that this "free" variant is in P for c=2. We also prove that for an unbounded number of colours, Flood-It remains NP-hard for boards of height at least 3, but is in P for boards of height 2. Next we show how a c-1 approximation and a randomised 2c/3 approximation algorithm can be derived, and that no polynomial time constant factor, independent of c, approximation algorithm exists unless P=NP. We then investigate how many moves are required for the "most demanding" n by n boards (those requiring the most moves) and show that the number grows as fast as Theta(n*c^0.5). Finally, we consider boards where the colours of the tiles are chosen at random and show that for c>=2, the number of moves required to flood the whole board is Omega(n) with high probability.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Sampling Colourings of the Triangular Lattice

We show that the Glauber dynamics on proper 9-colourings of the triangular lattice is rapidly mixing, which allows for efficient sampling. Consequently, there is a fully polynomial randomised approximation scheme (FPRAS) for counting proper 9-colourings of the triangular lattice. Proper colourings correspond to configurations in the zero-temperature anti-ferromagnetic Potts model. We show that the spin system consisting of proper 9-colourings of the triangular lattice has strong spatial mixing. This implies that there is a unique infinite-volume Gibbs distribution, which is an important property studied in statistical physics. Our results build on previous work by Goldberg, Martin and Paterson, who showed similar results for 10 colours on the triangular lattice. Their work was preceded by Salas and Sokal's 11-colour result. Both proofs rely on computational assistance, and so does our 9-colour proof. We have used a randomised heuristic to guide us towards rigourous results.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

The Complexity of Approximating Bounded-Degree Boolean #CSP (Extended Abstract)

The degree of a CSP instance is the maximum number of times that a variable may appear in the scope of constraints. We consider the approximate counting problem for Boolean CSPs with bounded-degree instances, for constraint languages containing the two unary constant relations {0} and {1}. When the maximum degree is at least 25 we obtain a complete classification of the complexity of this problem. It is exactly solvable in polynomial-time if every relation in the constraint language is affine. It is equivalent to the problem of approximately counting independent sets in bipartite graphs if every relation can be expressed as conjunctions of {0}, {1} and binary implication. Otherwise, there is no FPRAS unless NP=RP. For lower degree bounds, additional cases arise in which the complexity is related to the complexity of approximately counting independent sets in hypergraphs.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Strong Spatial Mixing and Rapid Mixing with Five Colours for the Kagome Lattice

We consider proper 5-colourings of the kagome lattice. Proper q-colourings correspond to configurations in the zero-temperature q-state anti-ferromagnetic Potts model. Salas and Sokal have given a computer assisted proof of strong spatial mixing on the kagome lattice for q>=6 under any temperature, including zero temperature. It is believed that there is strong spatial mixing for q>=4. Here we give a computer assisted proof of strong spatial mixing for q=5 and zero temperature. It is commonly known that strong spatial mixing implies that there is a unique infinite-volume Gibbs measure and that the Glauber dynamics is rapidly mixing. We give a proof of rapid mixing of the Glauber dynamics on any finite subset of the vertices of the kagome lattice, provided that the boundary is free (not coloured). The Glauber dynamics is not necessarily irreducible if the boundary is chosen arbitrarily for q=5 colours. The Glauber dynamics can be used to uniformly sample proper 5-colourings. Thus, a consequence of rapidly mixing Glauber dynamics is that there is fully polynomial randomised approximation scheme for counting the number of proper 5-colourings.

0 citations0 reviewsNo code linkedOpen access