Seminars in November 2011

  • Jon-Lark Kim (김종락), A New Class of Linear Codes for Cryptographic Uses
    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.

    Tags:

  • Satoru Iwata, Approximating Max-Min Weighted T-join
    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.
    Tags:

  • (Colloquium) Satoru Iwata, Submodular Optimization and Approximation Algorithms
    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.
    Tags:

Monthly Archives