Tag - Complexity theory

Saket Saurabh: Graph Isomorphism (on structured inputs)

18th January, 2022

The Graph Isomorphism (GI) problem is arguably the most widely known problem whose membership in P is unknown, but which is not believed to be NP-hard. While the existence of a polynomial-time algorithm on general graphs is still elusive, the complexity of Graph Isomorphism has been well understood on several classes of graphs, where structural properties of graphs in question have been used to design polynomial-time procedures solving the problem. In this talk we will look at some of these algorithms for Graph Isomorphism through the perspective of contributions of the speaker.

Alexander Ushakov: Quadratic equations in Baumslag-Solitar groups

19th November, 2021

We prove that the Diophantine problem for quadratic equations in unimodular and metabelian Baumslag-Solitar groups BS(m,n) is decidable and belongs to NP. Furthermore, the problem is polynomial-time decidable if |m|=|n|=1 and is NP-hard otherwise.

Vladimir Shpilrain: What, if anything, can be done in sublinear time?

4th February, 2021

In his talk on September 10, 2020, Yuri Gurevich discussed some algorithms that run in linear time (in the "length" of an input). We are going to take it up a notch and discuss what can be done in sublinear time; in particular, without reading the whole input but only a small part thereof. One well-known example is deciding divisibility of a decimal integer by 2, 5, or 10: this is done by reading just the last digit. We will discuss some less obvious examples from (semi)group theory.

Yuri Gurevich: What, if anything, can be done in linear time?

10th September, 2020

The answer to the title question seems to be "Not much". Even sorting n items takes n log(n) swaps. Actually, quite a bit can be done in linear time. In the first part of the talk we illustrate some known linear-time techniques (and pave the way to the second part).

Working on access control at Microsoft, we noticed that the most basic and useful access-control queries could be executed blazingly fast in practice. We wondered whether there was a theoretical foundation for the phenomenon. Eventually we came up with a logic calculus and an algorithm that, given a set of hypothesis and a set of queries, decides - in linear time - which of the queries follow from the hypotheses and which don't. In the second part of the talk, we explain how this is at all possible.

The presentation builds on joint work with Itay Neeman (UCLA Prof.), Carlos Cotrini and Ori Lahav (students at the time), and Artem Melentyev (a Microsoft intern at the time).

Zoran Šunić: Deciding if a right-angled Artin group is free-by-free is NP-complete

19th March, 2020

We show that deciding if a right-angled Artin group is free-by-free is an NP-complete problem. The work is based on an earlier result by Susan Hermiller and the speaker stating that the right-angled Artin group AΓ defined by the graph Γ is free-by-free if and only if Γ is 2-breakable (a graph Γ is 2-breakable if there exists an independent set D of vertices in Γ such that every cycle in Γ contains as least two vertices from D). We reduce the 3SAT Problem to the problem of deciding if a given graph is 2-breakable (in fact, k-breakable, for any fixed k ≥ 1). Once it is shown that the problem is NP-complete, it is not difficult to show that it stays NP-complete even if we restrict it to right-angled Artin groups defined by planar graphs. Note that the more special problem of deciding if a right-angled Artin group is free-by-infinite-cyclic has a very simple answer. Namely, it follows easily from known results that the following three statements are equivalent. (1) AΓ is free-by-infinite-cyclic. (2) Γ is a forest. (3) AΓ embeds in the right angled group defined by the path of length 3. (Joint work with David Carroll and Benjamin Francisco.)

Ashish Dwivedi: Counting basic-irreducible factors mod pk in deterministic poly-time and p-adic applications

29th March, 2019

Finding an irreducible factor, of a polynomial f(x) modulo a prime p, is not known to be in deterministic polynomial time. Though there is such a classical algorithm that counts the number of irreducible factors of f mod p. We can ask the same question modulo prime-powers pk. The irreducible factors of f mod pk blow up exponentially in number; making it hard to describe them. Can we count those irreducible factors mod pk that remain irreducible mod p? These are called {\em basic-irreducible}. A simple example is in f=x2+px mod p2; it has p many basic-irreducible factors. Also note that, x2+p mod p2 is irreducible but not basic-irreducible!

We give an algorithm to count the number of basic-irreducible factors of f mod pk in deterministic poly(deg(f),k log p)-time. This solves the open questions posed in (Cheng et al, ANTS'18 and Kopp et al, Math. Comp. '19). In particular, we are counting roots mod pk; which gives the first deterministic poly-time algorithm to compute Igusa zeta function of f. Also, our algorithm efficiently partitions the set of all basic-irreducible factors (possibly exponential) into merely deg(f)-many disjoint sets, using a compact tree data structure and split ideals.