Theoretical Computer Science seminars

Upcoming Seminars

21.11.2019 - Joel Day (Lboro): "Simple" Word Equations and Their Solutions
Abstract:

    Word equations are equations in which the variables take values from the set of words over some given alphabet. They provide a fundamental framework for reasoning about the structure of sequences and as such, remain an important topic at the intersection of theoretical computer science and algebra, with applications in areas such as databases and software verification. Since the famous result of Makanin, it has been known that whether a given word equation has a solution can be decided algorithmically. However, the (computational) complexity of algorithms solving word equations remains very high and is still not well understood, and solving word equations in the real world, with limited resources, remains particularly challenging. This difficulty is compounded by the fact that with most applications, it is important to know whether solutions exist satisfying some additional constraints, for example, relating the lengths of variables, or restriction of a variable to a regular language.

    This talk will focus on 'simple' word equations, whose structure are restricted but for which many of the most important questions remain unanswered, along with recent efforts to understand the structure of their solutions. Results in this direction are useful not only as a potential base for understanding more general cases, but also have the potential to be practically useful, since many of the equations encountered in applications are not structurally complex. Moreover, there is more potential in these restricted cases for a more detailed understanding of the complete set of solutions, which is often necessary for working with variants of the problem involving additional constraints.


05.12.2019 - Sam Thompson (Lboro): Dynamic Complexity of Documents Spanners
Abstract:

    This talk is on the dynamic complexity of document spanners. Document spanners are a formal framework of information extraction which allows us to query text like we would a relational database. The question we investigate is, what is the complexity of computing the results of these queries if the text is subject to updates?

    To investigate this question, we used the dynamic complexity framework, which defines complexity classes based on the logic needed to write update formulas for a given query. These update formulas are used to keep the result of a query correct when updates to a database occur. If we can write such update formulas, then we can “maintain” that query. In our work, we show that the class of regular spanners can be maintained by the dynamic complexity class DynPROP (update formulas are in quantifier free first-order logic), that the class DynCQ (update formulas are conjunctive queries) is more expressive than the class of core spanners, and that the class DynFO (update formulas are in first order logic) is more expressive than generalized core spanners.


19.12.2019 - TBD (TBD): TBA
Abstract:

    TBA.

Previous Seminars


07.11.2019 - Dominik Freydenberger (Lboro): A Finite Model Theory of Concatenation
Abstract:

    This talk is about different two different approaches to logic on words, and a new logic that aims to combine them.

    Essentially, core spanners use regular expressions with variables to turn the input text into tables of positions in the text, which can then be manipulated and combined with the relational operators projection, join, union, and string equality selection. 

    The full definition of semantics of core spanners is not exactly lightweight, which complicates tasks like examining their expressive power. Luckily, there is an alternative: SpLog is a fragment of the existential theory of concatenation that has the same expressive power as core spanners (and one can convert efficiently between SpLog and core spanners). 

    The simple syntax and semantics of SpLog avoid many of the annoyances in the definitions for core spanners. Furthermore, the connections to pattern languages and word equations allow us to directly apply various results from these areas. 

    Immediate consequences and applications include an alternative way of defining relations for spanners, a pumping lemma for core spanners, and insights into the relative succinctness of various classes of spanner representations and their connection to graph querying languages.

This talk is based on the very recent extended journal version of my paper “A Logic for Document Spanners” (ICDT 2017).


28.03.2019 - Shaheen Fatima (Lboro): Computing optimal coalition structures in polynomial time
Abstract:
    We address the problem of computing an optimal partition of a set. Each partition has a value and the problem is to find a partition with the highest value. This problem is in general computationally hard. We show how the problem can be solved in polynomial time if the values are monotonic and there is a unique optimum..

14.03.2019 - Amitabh Trehan (Lboro): Sending and Forgetting: Flooding and Self-Healing Routing over Low Memory Nodes
Abstract:
    Imagine a network where every user is very aggressive about forwarding the messages they receive (like hyperactive WhatsApp users). Only constraint is that they don’t send it back to the users they received the message from in the same round. However, they quickly forget all this information and will forward the same message if they get it again! This is a restatement of the classic flooding algorithm in distributed computing.
    Will this process ever stop? We have a somewhat surprising result.
This is ongoing work with Walter Hussak.

28.02.2019 - Joel Day (Lboro): How hard is solving "simple" word equations?
Abstract:
    Word equations are equations in which the variables take values from the set of words over some specified alphabet. They provide a fundamental framework for reasoning about the structure of words and as such, have remained an important topic in the intersection of algebra and theoretical computer science.
    Since the famous result of Makanin, it has been known that whether a given word equation has a solution is algorithmically decidable. Nevertheless, the best known complexity upper bound is (non-deterministic) linear space, and solving word equations in practice remains challenging. Moreover, it is straightforward to show that the problem is NP-hard, even for quadratic equations (in which each variable is restricted to at most two occurrences). Resolving the exact complexity, even in the quadratic case, remains a long standing and seemingly very difficult open problem. 
    This talk will focus on the complexity of even more restricted forms of word equations with a view to progressing to more general classes. In particular, we have shown that the NP-hardness lower bound is retained even in severely restricted variants, and present an approach for reasoning about the (non)-minimality of solutions to quadratic equations which can be used to obtain corresponding upper bounds in certain cases, as well as providing an interesting link to the topic of avoidability of patterns.

31.01.2019 - Lars Nagel (Lboro): Randomized Renaming in Shared Memory Systems
Abstract:
    Renaming is a task in distributed computing where n processes are assigned new names from a name space of size m. The problem is called tight if m = n, and loose if m > n. In recent years renaming came to the fore again and new algorithms were developed. For tight renaming in asynchronous shared memory systems, Alistarh et al. describe a construction based on the AKS network that assigns all names within O(log n) steps per process. They also show that, depending on the size of the name space, loose renaming can be done considerably faster. For m = (1 + q) * n and constant q, they achieve a step complexity of O(loglog n).
    My talk is based on the paper "Randomized Renaming in Shared Memory Systems". It considers tight as well as loose renaming and introduces randomised algorithms that achieve their tasks with high probability. The model assumed is the asynchronous shared memory model against an adaptive adversary. The algorithm for loose renaming maps n processes to a name space of size m = (1 + 2/(log n)^k) * n = (1+o(1)) * n performing O(k * (loglog n)^2) test-and-set operations. For tight renaming, the protocol presented assigns n processes to n names with step complexity O(log n), but without the overhead andimpracticality of the AKS network. This algorithm utilizes modern hardware features in form of a counting device.

17.01.2019 - Marie Lejeune (Liège): Computing the k-binomial complexity of the Thue-Morse word
Abstract:
    In this talk, we will first recall some elementary notions in combinatorics on words such as morphisms and their fixed points, factors, subwords and the factor complexity of a word.
     We will then introduce the k-binomial equivalence relation. Two finite words u and v are equivalent for this relation if, for all words x of length at most k, x occurs as a subword of u as many times as of v. The next step will be to define the k-binomial complexity function of a word w, which maps every nonnegative integer n to the number of length-n factors occurring in w, up to k-binomial equivalence.
     Pavel Salimov and Michel Rigo showed in 2015 that the k-binomial complexity function of the Thue-Morse word is bounded by a constant, depending on k. They also proved that the k-binomial complexity and the factor complexity of any Sturmian word are equal. This result is surprinsingly different from the classical Morse-Hedlund theorem. For that reason, a joint work with Julien Leroy and Michel Rigo led to the computation of the exact value taken by the k-binomial complexity function of the Thue-Morse word. The main results obtained in this work will be presented and illustrated.

06.12.2018 - Laura Hutchinson (Lboro): On Parikh matrices and the reduction of their ambiguity
Abstract:
    Parikh matrices can be used to denote words, based on the number of subwords present in these words. However, whilst a word is associated to only one Parikh matrix, a single matrix does not necessarily describe a single word, but rather can describe multiple. This problem is referred to as the ambiguity of a Parikh matrix. We first explain this problem in greater detail and then go on to demonstrate a method that reduces this ambiguity; L-Parikh matrices. These are Parikh matrices calculated using the Lyndon conjugate of the original word in question. We show the specific cases where L-Parikh matrices reduce ambiguity, based on the properties of the words associated to the Parikh matrix.

22.11.2018 - Gary Bennett (Lboro): On the Complexity of the Growing Kingdom Leader Election algorithm
Abstract:
    In distributed computing, leader election is the process of designating a single processor as the organiser of some task.
     In 2015 KPPRT's JACM paper they proposed a new deterministic universal leader election algorithm, known as the Double-Win Growing Kingdom LE algorithm. Their algorithm "grows kingdoms" with leader candidates continuing to grow their kingdoms (by building BFS trees) until there is just one kingdom left.
     In this talk, we present their original analysis and our own that improves the time complexity from O(D log n) to O(D) and message complexity from O(m log n) to O(m log D), Where n denotes the number of processors in the network, m denotes the number of edges in the network, and D denotes the diameter of the network.
     This answers the open question of whether the running time can be improved to O(D), with the same number of messages, in the deterministic case.

08.11.2018 - Alex M. Smith (Lboro): On Maximal-exponent factors
Abstract:
    In this talk I will present an improved lower bound on the number of occurrences of maximal-exponent factors present in a word. That is, I will show that there exist infinite words in which the number of maximal-exponent factors in every prefix is greater than 9/10 of the prefix's length. Furthermore, the presented construction of infinite words with prefixes fulfilling the previous condition utilises only a finite alphabet whose size can be bounded.

24.10.2018 - Florin Manea (Kiel University): Fast Rollercoasters
Abstract:
    A rollercoaster is a sequence of real numbers for which every maximal contiguous subsequence - increasing or decreasing - has length at least three. By translating this sequence to a set of points in the plane, a rollercoaster can be defined as an x-monotone polygonal path for which every maximal sub-path, with positive- or negative-slope edges, has at least three vertices. Given a sequence of distinct real numbers, the rollercoaster problem asks for a maximum-length (not necessarily contiguous) subsequence that is a rollercoaster. It was conjectured that every sequence of n distinct real numbers contains a rollercoaster of length at least ceil[n/2] for n>7, while the best known lower bound is Omega(n/log n). In our [ICALP 2018] paper we prove this conjecture. Our proof was constructive and implies a linear-time algorithm for computing a rollercoaster of this length. Extending the O(n log n)-time algorithm for computing a longest increasing subsequence, we show how to compute a maximum-length rollercoaster within the same time bound. A maximum-length rollercoaster in a permutation of {1,...,n} can be computed in O(n log log n) time. We recently improved these results from [ICALP 2018] and showed that a longest rollercoaster can be computed in linear time.
    The search for long rollercoasters was motivated by orthogeodesic point-set embedding of caterpillars. A caterpillar is a tree such that deleting the leaves gives a path, called the spine. A top-view caterpillar is one of maximum degree 4 such that the two leaves adjacent to each vertex lie on opposite sides of the spine. As an application of our result on rollercoasters, we were able in the [ICALP 2018] paper to find a planar drawing of every n-vertex top-view caterpillar on every set of 25/3(n+4) points in the plane, such that each edge is an orthogonal path with one bend. This improved the previous best known upper bound on the number of required points, which is O(n log n). We also showed that such a drawing can be obtained in linear time, when the points are given in sorted order.

This is based on the works:
Therese C. Biedl, Ahmad Biniaz, Robert Cummings, Anna Lubiw, Florin Manea, Dirk Nowotka, Jeffrey Shallit: Rollercoasters and Caterpillars. ICALP 2018: 18:1-18:15
Pawel Gawrychowski, Florin Manea, Radoslav Serafin: Fast and Longest Rollercoasters submitted.

05.07.2018 - Lucas Bueri (École Normale Supérieure Paris-Saclay): Shortlex normal forms for R-trivial languages
Abstract:
    R-trivial languages are a subclass of regular languages. There exist various different characterisations of these languages. For instance, they can be described by a Boolean combination of languages expressions of the form A_0^* a_1 A_1^* … a_k A_k^* where a_i is not in the set of letters A_{i-1}. Equivalently, these languages are those accepted by partially-ordered deterministic finite automata. The third characterisation is a restricted fragment of linear temporal logic.
    Each of these characterisations yields a congruences indexed by the size of the relative objects. For each such congruence, we develop a linear time algorithm to compute the shortlex normal form of a given word. 
This is joint work with Manfred Kufleitner.

21.06.2018 - Ferruh Ozbudak (Middle East Technical University): Construction of Some Codes Suitable for Countermeasures to Both Side Channel Attacks and Fault Injection Attacks
Abstract:
    Using algebraic curves over finite fields we construct some codes suitable for being used in the countermeasure called Direct Sum Masking which allows when properly implemented to protect the whole cryptographic block cipher algorithm against side channel attacks and fault injection attacks simultaneously.
This is a joint work with Claude Carlet, Cem Guneri and Sihem Mesnager.

07.06.2018 - Ana Sălăgean (Lboro): Counting "fast points" for higher order differential attacks on ciphers
Abstract:

    We first give an introduction to discrete derivatives of Boolean functions and their use in cryptographic attacks. This type of attacks, called higher order differential attacks, became popular with the "cube" attack introduced by Dinur and Shamir in 2009 and successfully used for braking reduced versions of the stream cipher Trivium and of some other ciphers (see also earlier attacks by Lai, O'Neil, Vielhaber, etc). 

    We investigate the notion of “fast points” for a binary polynomial function f i.e. vectors such that the discrete derivative of f in the direction of this vector has a lower than expected degree. Fast points were introduced by Duan and Lai, motivated by the fact that higher order differential attacks are usually more efficient if they use such points. The number of functions which admit fast points were computed by Duan et al in a small number of particular cases; we give recurrences and explicit formulae for all cases and discuss the cryptographic significance of these results.

17.05.2018 - Jonas Lefèvre (Lboro): Proving some Self-Stabilizing Algorithms
Abstract:

    Self-stabilizing algorithms are powerful tools against difficult situations, they can recover from any faulty state caused by transient faults. And with great power comes great difficulties to construct and prove the algorithms. 

    I will present some algorithms and show the kind of proofs/technics hat are used to deal with them.


03.05.2018 - Manfred Kufleitner (Lboro): 
Yet another proof of Parikh’s Theorem
Abstract:
    Parikh’s Theorem is a classical tool in formal language theory. There is a “logic” version of it due to Verma, Seidl, and Schwentick. For the latter, a new and simple proof will be presented.

19.04.2018 - Dominik Freydenberger (Lboro): 
A Logic for Core Spanners
Abstract:

    Core spanners are a formal framework for information extraction that was introduced by Fagin, Kimelfeld, Reiss, and Vansummeren (PODS 2013, JACM 2015) to study properties of the query language AQL that is used in IBM's SystemT (think “like SQL, but for searching in text”). 

    Essentially, core spanners use regular expressions with variables to turn the input text into tables of positions in the text, which can then be manipulated and combined with the relational operators projection, join, union, and string equality selection. 

    The full definition of semantics of core spanners is not exactly lightweight, which complicates tasks like examining their expressive power. Luckily, there is an alternative: SpLog is a fragment of the existential theory of concatenation that has the same expressive power as core spanners (and one can convert efficiently between SpLog and core spanners). 

    The simple syntax and semantics of SpLog avoid many of the annoyances in the definitions for core spanners. Furthermore, the connections to pattern languages and word equations allow us to directly apply various results from these areas. 

    Immediate consequences and applications include an alternative way of defining relations for spanners, a pumping lemma for core spanners, and insights into the relative succinctness of various classes of spanner representations and their connection to graph querying languages.

This talk is based on the very recent extended journal version of my paper “A Logic for Document Spanners” (ICDT 2017).