Browsing by Author "Thakkar, Dhara"

For a finite group G, the size of a minimum generating set of G is denoted by d(G). Given a finite group G and an integer k, deciding if d(G)?k is known as the minimum generating set (MIN-GEN) problem. A group G of order n has generating set of size logpn? where p is the smallest prime dividing n=|G|. This fact is used to design an nlogpn+O(1)-time algorithm for the group isomorphism problem of groups specified by their Cayley tables (attributed to Tarjan by Miller, 1978). The same fact can be used to give an nlogpn+O(1)-time algorithm for the MIN-GEN problem. We show that the MIN-GEN problem can be solved in time n(1/4)logpn+O(1) for general groups given by their Cayley tables. This runtime incidentally matches with the runtime of the best known algorithm for the group isomorphism problem. We show that if a group G, given by its Cayley table, is the product of simple groups then a minimum generating set of G can be computed in time polynomial in |G|. Given groups Gi along with d(Gi) for i?[r] the problem of computing d(?i?[r]Gi) is nontrivial. As a consequence of our result for products of simple groups we show that this problem also can be solved in polynomial time for Cayley table representation. For the MIN-GEN problem for permutation groups, to the best of our knowledge, no significantly better algorithm than the brute force algorithm is known. For an input group G?Sn, the brute force algorithm runs in time |G|O(n) which can be 2?(n2). We show that if G?Sn is a primitive permutation group then the MIN-GEN problem can be solved in time quasi-polynomial in n. We also design a DTIME(2n) algorithm for computing a minimum generating set of permutation groups all of whose non-abelian chief factors have bounded orders.

A finite group of order n can be represented by its Cayley table. In the word-RAM model the Cayley table of a group of order n can be stored using O(n²) words and can be used to answer a multiplication query in constant time. It is interesting to ask if we can design a data structure to store a group of order n that uses o(n²) space but can still answer a multiplication query in constant time. Das et al. (J Comput Syst Sci 114:137–146, 2020) showed that for any finite group G of order n and for any δ∈[1/logn,1], a data structure can be constructed for G that uses O(n^1+δ/δ) space and answers a multiplication query in time O(1/δ). Farzan and Munro (ISSAC, 2006) gave an information theoretic lower bound of Ω(n) on the number of words to store a group of order n. We design a constant query-time data structure that can store any finite group using O(n) words where n is the order of the group. Since our data structure achieves the information theoretic lower bound and answers queries in constant time, it is optimal in both space usage and query-time. A crucial step in the process is essentially to design linear space and constant query-time data structures for nonabelian simple groups. The data structures for nonabelian simple groups are designed using a lemma that we prove using the Classification Theorem for Finite Simple Groups.

A finite group of order n can be represented by its Cayley table. In the word-RAM model the Cayley table of a group of order n can be stored using O(n²) words and can be used to answer a multiplication query in constant time. It is interesting to ask if we can design a data structure to store a group of order n that uses o(n²) space but can still answer a multiplication query in constant time. We design a constant query-time data structure that can store any finite group using O(n) words where n is the order of the group. Farzan and Munro (ISSAC 2006) gave an information theoretic lower bound of Ω(n) on the number of words to store a group of order n. Since our data structure achieves this lower bound and answers queries in constant time, it is optimal in both space usage and query-time. A crucial step in the process is essentially to design linear space and constant query-time data structures for nonabelian simple groups. The data structures for nonableian simple groups are designed using a lemma that we prove using the Classification Theorem for Finite Simple Groups (CFSG).

For any fixed positive integer r and a given budget k, the r-Eigenvalue Vertex Deletion (r-EVD) problem asks if a graph G admits a subset S of at most k vertices such that the adjacency matrix of G \ S has at most r distinct eigenvalues. The edge deletion, edge addition, and edge editing variants are defined analogously. For r = 1, r-EVD is equivalent to the Vertex Cover problem. For r = 2, it turns out that r-EVD amounts to removing a subset S of at most k vertices so that G \ S is a cluster graph where all connected components have the same size. We show that r-EVD is NP-complete even on bipartite graphs with maximum degree four for every fixed r > 2, and FPT when parameterized by the solution size and the maximum degree of the graph. We also establish several results for the special case when r = 2. For the vertex deletion variant, we show that 2-EVD is NP-complete even on triangle-free and 3d-regular graphs for any d ≽ 2, and also NP-complete on d-regular graphs for any d ≽ 8. The edge deletion, addition, and editing variants are all NP-complete for r = 2. The edge deletion problem admits a polynomial time algorithm if the input is a cluster graph, while – in contrast – the edge addition variant is hard even when the input is a cluster graph. We show that the edge addition variant has a quadratic kernel. The edge deletion and vertex deletion variants admit a single-exponential FPT algorithm when parameterized by the solution size alone. Our main contribution is to develop the complexity landscape for the problem of modifying a graph with the aim of reducing the number of distinct eigenvalues in the spectrum of its adjacency matrix. It turns out that this captures, apart from Vertex Cover, also a natural variation of the problem of modifying to a cluster graph as a special case, which we believe may be of independent interest.

The celebrated result by Ben-Or and Cleve [SICOMP92] showed that algebraic formulas are polynomially equivalent to width-3 algebraic branching programs (ABP) for computing polynomials. i.e., VF = VBP3. Further, there are simple polynomials, such as ^P8i=1 xiyi, that cannot be computed by width-2 ABPs [Allender and Wang, CC16]. Bringmann, Ikenmeyer and Zuiddam, [JACM18], on the other hand, studied these questions in the setting of approximate (i.e., border complexity) computation, and showed the universality of border width-2 ABPs, over fields of characteristic ≠ 2. In particular, they showed that polynomials that can be approximated by formulas can also be approximated (with only a polynomial blowup in size) by width-2 ABPs, i.e., VF = VBP2. The power of border width-2 algebraic branching programs when the characteristic of the field is 2 was left open. In this paper, we show that width-2 ABPs can approximate every polynomial irrespective of the field characteristic. We show that any polynomial f with ℓ monomials and with at most t odd-power indeterminates per monomial can be approximated by O(ℓ· (deg(f) + 2^t))-size width-2 ABPs. Since ℓ and t are finite, this proves universality of border width-2 ABPs. For univariate polynomials, we improve this upper-bound from O(deg(f)²) to O(deg(f)). Moreover, we show that, if a polynomial f can be approximated by small formulas, then the polynomial f^d, for some small power d, can be approximated by small width-2 ABPs. Therefore, even over fields of characteristic two, border width-2 ABPs are a reasonably powerful computational model. Our construction works over any field.

Let n be a positive integer greater than 2. We define the Proth numerical semigroup, Pk(n), generated by {k2n+i+1∣i∈N}, where k is an odd positive number and k< 2 ⁿ. In this paper, we introduce the Frobenius problem for the Proth numerical semigroup Pk(n) and give formulas for the embedding dimension of Pk(n). We solve the Frobenius problem for Pk(n) by giving a closed formula for the Frobenius number. Moreover, we show that Pk(n) has an interesting property such as being Wilf.

Let n be a positive integer greater than 2. We define \textit{the Proth numerical semigroup}, Pk(n), generated by {k2n+i+1?i?N}, where k is an odd positive number and k<2n. In this paper, we introduce the Frobenius problem for the Proth numerical semigroup Pk(n) and give formulas for the embedding dimension of Pk(n). We solve the Frobenius problem for Pk(n) by giving a closed formula for the Frobenius number. Moreover, we show that Pk(n) has an interesting property such as being Wilf.

The minimal faithful permutation degree 𝜇⁡(𝐺) of a finite group 𝐺 is the smallest integer 𝑚 for which there is an injective homomorphism 𝜙 from 𝐺 to 𝑆𝑚. The main result of this paper is a randomized polynomial-time algorithm for computing the minimal faithful permutation degree groups without abelian normal subgroups. Additionally, we show that: 1. For any primitive permutation group 𝐺, 𝜇⁡(𝐺) can be computed in quasi-polynomial time. 2. For a group 𝐺 given by its Cayley table, 𝜇⁡(𝐺) can be computed in DSPACE⁡(log3⁡|𝐺|).

Cayley's theorem says that every finite group G can be viewed as a subgroup of a symmetric group Sm for some integer m. The minimal faithful permutation degree μ(G) of a finite group G is the smallest integer m such that there is an injective homomorphism φ from G to Sm. The main result of this paper is a randomized polynomial time algorithm for computing the minimal faithful permutation degree of semisimple permutation groups. Semisimple groups are groups without any abelian normal subgroups. Apart from this, we show that: 1. For any primitive permutation group G, μ(G) can be computed in quasi-polynomial time. 2. Given a permutation group G and an integer k, the problem of deciding if μ(G) ≤ k is in NP. 3. For a group G given by its Cayley table, μ(G) can be computed in DSPACE(log³ |G|).

Let G be a finite group. In order to determine the smallest cardinality d(G) of a generating set of G and a generating set with this cardinality, one should repeat many times the test whether a subset of G of small cardinality generates G. We prove that if a chief series of G is known, then the numbers of these generating tests can be drastically reduced. At most |G|13/5 subsets must be tested. This implies that the minimum generating set problem for a finite group G can be solved in polynomial time.

Let G be a finite group. In order to determine the smallest cardinality d(G) of a generating set of G and a generating set with this cardinality, one should repeat ‘many times’ the test whether a subset of G of ‘small’ cardinality generates G. We prove that if a chief series of G is known, then the numbers of these ‘generating tests’ can be drastically reduced. At most |G|^13/5 subsets must be tested. This implies that the minimum generating set problem for a finite group G can be solved in polynomial time.