Thesis topic suggestions

MS THESIS (To be co-supervised with Caner Taskin)

Multiplying two polynomials in an efficient way is a fundamental problem in cryptology and computer science in general. Since floating-point numbers are expressed in base 2, multiplying two floating-point numbers is equivalent to multiplying two univariate polynomials (Cenk and Ozbudak, 2010).

Given two univariate polynomials, we can obtain their product by multiplying all the cross terms. Given a polynomial a(x) of degree n (the largest power is n), and a polynomial b(x) of degree m (the largest power is m), the product, ab, will have degree n+m. To compute the product ab, there will be up to (n+1)(m+1) cross terms to multiply.

One measure of efficiency is the number of multiplication operations while computing all the coefficients in ab. In other words, we neglect the cost of the summation and subtraction operations, and we only count the total number of multiplication operations. As an example, take two polynomials

a(x)=a0+a1x

b(x)=b0+b1x

then c:=a(x)b(x)=a0b0 + (a0b1+a1b0)x + a1b1 x2

where c0= a0b0, c1 = a0b1+a1b0 and c2= a1b1 and a total of 4 multiplications in used to obtain these coefficients. However, by computing c1=(a0+a1)(b0+b1)- a0b0 - a1b1, we would use only 3 multiplications to obtain all of c0, c1 and c2.

Karatsuba Algorithm (Karatsuba and Ofman, 1963) is a well-known heuristic method to multiply two polynomials efficiently. When the coefficients of the given polynomials are defined to be 0 or 1, then it is known that the minimum number of multiplications needed to multiply two polynomials of degree 1 is 3, of degree 2 is 6, of degree 3 is 9, of degree 4 is 13. For degree 5 polynomials the best known bound is 17, however it is not known if it is the optimal (Montgomery, 2005). This thesis is about formulating this problem of minimizing the number of multiplications to multiply two polynomials as an integer program and developing solution procedures (using decomposition methods) to solve it.

Requirements: Good programming skills in C++, CPLEX or GUROBI, IE 613 (Large Scale Programming) or consent of the supervisors

References:

Karatsuba, A., & Ofman, Y. (1963). In Multiplication of multidigit numbers on automata, Vol. Soviet Physics Doklady: Russia, 595-595.
Montgomery, P. L. (2005). Five, six, and seven-term Karatsuba-like formulae. IEEE Transactions on Computers, 54(3), 362-369.
Cenk, M., & Özbudak, F. (2010). On multiplication in finite fields. Journal of Complexity, 26(2), 172-186.

MS THESIS (To be co-supervised with Caner Taskin)

Solving the Defensive Domination Problem using Integer Programming techniques

Defensive domination: a k-attack is a subset of at most k vertices. A k-defense is a one-to-one assignment of defenders to a k-attack (a defender can also defend against an attack on itself). A set D is a k-defensive set if it can defend against ANY k-attack. The defensive domination problem is to find a k-defensive dominating set of minimum cardinality. Deciding whether there is a k-defensive dominating set of size at most t is known to be NP-complete for fixed k; if k is part of the input, the problem is not even in NP. There are only very few special graph classes where the k-defensive dominating set can be solved in polynomial time. No Integer Programming formulation has been suggested in the literature. The student will suggest IP formulations for the defensive domination problem and develop solution procedures.

Requirements: Good programming skills in C++, CPLEX or GUROBI. IE 613 (Large Scale Programming); or consent of the supervisors

References:

T. Ekim, A. Farley, A. Proskurowski, The Complexity of the Defensive Domination Problem in Special Graph Classes, Discrete Mathematics, 343 (2), Feb 2020, 111665. doi: 10.1016/j.disc.2019.111665
T. Ekim, A. Farley, A. Proskurowski, M. Shalom, Defensive Domination in Proper Interval Graphs, submitted. http://arxiv.org/abs/2010.03865

MS THESIS (To be co-supervised with Caner Taskin)

Maximum Acyclic Matching

A matching M in a graph G ıs acyclic if the subgraph of G induced by the set of vertices that are incident to an edge in M is a forest. If ν(G), νac(G), and νs(G) denote the largest size of a matching, an acyclic matching, and an induced matching in G, respectively, then, since every induced matching is acyclic, we have ν(G) ≥ νac(G) ≥ νs(G). In contrast to the matching number ν(G), which is a well known classical tractable graph parameter, both, the acyclic matching number νac(G) as well as the induced matching number νs(G) are computationally hard. While induced matchings have been studied in great detail, only few results are known on the acyclic matching number. While the equality ν(G) = νs(G) can be decided efficiently for a given graph G, it is NP-complete to decide whether ν(G) = νac(G) for a given bipartite graph G of maximum degree at most 4, and efficient algorithms computing the acyclic matching number are known only for certain graph classes.

This project is about

1) Identifying graph classes where νac(G) can be computed in polynomial time, if possible, and

2) Developing Integer Programming Formulations and approximation algorithms for the Max Acyclic Matching Problem and testing their performance with experiments.

References:

Useful Links