Archive for the ‘2011’ Category

Ilkyoo Choi (최일규), Avoiding Large Squares in Partial Words

Friday, December 2nd, 2011
Avoiding Large Squares in Partial Words
Ilkyoo Choi (최일규)
Department of Mathematics, University of Illinois at Urbana-Champaign, IL, USA
2011/12/22 Thu 4PM-5PM
Given a fixed alphabet, a word of length n is an n-tuple with entries in the alphabet. A hole is a character outside the alphabet that is viewed as representing any letter of the alphabet. A partial word is a string where each character is a hole or belongs to the alphabet. Two partial words having the same length are compatible if they agree at each position where neither has a hole.
A square is a word formed by concatenating two copies of a single word (no holes). A partial word W contains a square S if S is compatible with some (consecutive) subword of W. Let g(h,s) denote the maximum length of a binary partial word with h holes that contains at most s distinct squares. We prove that g(h,s)=∞ when s≥4 and when s=3 with h∈{0,1,2}; otherwise, g(h,s) is finite. Furthermore, we extend our research to cube-free binary partial words.
This is joint work with Dr. Francine Blanchet-Sadri and Robert Mercas.

Stefan Gruenewald, Quartets in Weakly Compatible Split Systems

Friday, November 18th, 2011
Quartets in Weakly Compatible Split Systems
Stefan Gruenewald
CAS-MPG Partner Institute for Computational Biology, Shanghai, China
2011/12/9 Fri 4PM-5PM (Room 3433)
A phylogenetic (i.e evolutionary) tree can be interpreted as a compatible split system, that is a collection of bipartitions of a finite set X such that, for all four elements of X, there are no two bipartitions in the collection that induce different splits of those four elements into two pairs. Such a split of a 4-set into two 2-sets is called a quartet, and a split system is said to display a quartet, if there is at least one split in the system that induces this quartet. In phylogenetics, it is often useful to allow more general than compatible split systems, in order to display contradicting signals in the data or to find evidence for reticulate evolution. One natural such generalization are weakly compatible split systems, where for every 4-set at most two of the three possible quartets are allowed to be displayed. The split decomposition algorithm (implemented in the Splitstree software) is a successful tool to construct weakly compatible split systems from distance data. However, weakly compatible split systems are not as well understood as compatible ones. For example, maximal compatible split systems, i.e. compatible split systems which become incompatible whenever a new split is added, correspond to binary trees and display one quartet for every 4-set. In contrast, maximal weakly compatible split systems often display less than the two quartets per 4-set that are allowed by definition. Indeed there are examples where no quartet is displayed for almost all 4-sets. This leaves the question what is the minimum cardinality of maximal weakly compatible split systems for given cardinality of X.
In my talk I will introduce weakly compatible split systems and explain their relevance for phylogenetics, and I will present upper and lower bounds for the smallest number of quartets in maximal weakly compatible split systems.

Jon-Lark Kim (김종락), A New Class of Linear Codes for Cryptographic Uses

Monday, November 7th, 2011
A New Class of Linear Codes for Cryptographic Uses
Jon-Lark Kim (김종락)
Department of Mathematics, University of Louisville, Louisville, KY, USA
2011/11/25 Fri 2PM-3PM

We introduce a new class of rate one half codes, called complementary information set codes. A binary linear code of length 2n and dimension n is called a complementary information set code (CIS code for short) if it has two disjoint information sets. This class of codes contains self-dual codes as a subclass. It is connected to graph correlation immune functions of use in the security of hardware implementations of  cryptographic primitives. In this talk, we give optimal or best known CIS codes of length <132. We  derive general constructions based on cyclic codes, double circulant codes, strongly regular graphs, and doubly regular tournaments. We derive a Varshamov-Gilbert bound for long CIS codes, and show that they can all be classified in small lengths up to 12 by the building up construction. This is a joint work with Claude Carlet, Philippe Gaborit, and Patrick Sole.

Satoru Iwata, Approximating Max-Min Weighted T-join

Thursday, September 15th, 2011
Approximating Max-Min Weighted T-join
Satoru Iwata
RIMS, Kyoto University, Kyoto, Japan
2011/11/11 Fri 4PM-5PM
Given an even subset T of the vertices of an undirected graph, a T-join is a subgraph in which the subset of vertices with odd degree is exactly T. Given edge weights, the weighted T-join problem is to find a T-join of minimum weight. With nonnegative edge weights, the problem can be reduced to finding a minimum weight perfect matching on the metric completion of the vertices in T.
Given an undirected graph with nonnegative edge weights but no specific T, the Max-Min Weighted T-join problem is to find an even cardinality vertex subset T such that the minimum weight T-join for this set is maximum. The unweighted case of the problem when all weights are either unit or infinity has been well characterized by a decomposition of the underlying graph into factor critical and matching-covered bipartite subgraphs (Frank1993). We consider the weighted version which is NP-hard even on a cycle. After showing a simple exact solution on trees, we present a 2/3-approximation algorithm for the general case. Our algorithm is based on a natural cut packing upper bound obtained using an LP relaxation and uncrossing, and relating it to the T-join problem using duality.
This is a joint work with R. Ravi.

(Colloquium) Satoru Iwata, Submodular Optimization and Approximation Algorithms

Thursday, September 15th, 2011
Submodular Optimization and Approximation Algorithms
Satoru Iwata
RIMS, Kyoto University, Kyoto, Japan
2011/11/10 Thu 4PM-5PM
Submodular functions are discrete analogues of convex functions. Examples include cut capacity functions, matroid rank functions, and entropy functions. Submodular functions can be minimized in polynomial time, which provides a fairly general framework of efficiently solvable combinatorial optimization problems. In contrast, the maximization problems are NP-hard and several approximation algorithms have been developed so far.
In this talk, I will review the above results in submodular optimization and present recent approximation algorithms for combinatorial optimization problems described in terms of submodular functions.