ISW - 2008 Program

Date
Mon
Tue
Wed
Thr
Fri
Chair
Ghanashyam Date
Chair
Geevarghese Philip
Chair
Pooja Singla
Chair
Sreejith
Chair
Neeldhara Misra
10:00 - 10:25
Nick Gill
The Thompson groups
Invariant subspaces for groups of discrete Fourier transform type operators
Venkatesh Raman
Vertex Cover: Parameterizing Above the Matching Number
Kapil Paranjape
What is Reciprocity?
Venkata Suryanarayana Nemani
Counting Giants
10:25 - 10:50
R Ramanujam
Free and fair e-elections
S Sheerazuddin
Modelling and verification of web services
Sridhar
Local Control of Global Chaos in Excitable Media.
Sitabhra Sinha
Understanding the Mind of a Worm
N Narayanan
The Discharging Method
10:50 - 11:15
Arunagiri
Zitterbewegung in Graphene
Nilanjan
What do we get by "boiling" strings?
Veerendra Vickram Awasthi
Homology of Generalized Hawaiian Earring
Sunil Simon
Games for distributed systems
Rahul Siddharthan
How DNA evolves, and how to trace its ancestry
11:15 - 11:45

Tea/Coffee Break

Chair
Somdeb Ghose
Chair
Sabapathi Krishnakumar
Chair
Praveen M
Chair
Sandipan Sengupta
Chair
Kamal Lodaya
11:45 - 12:10
Parameswaran Sankaran
Coarse geometry of groups
Rahul Sinha
Anomalies in B meson decays: Can they be signals of New Physics?
Gautam Menon
Cell division as a pattern formation problem
Sujay Ashok
D-branes as Matrix Factorizations
Amit Kumar Bhattacharjee
Statics and Kinetics of Nematic liquid crystals
12:10 - 12:35
Praveen M
Reachability problem in Petri nets
Noncommutative Polynomial Identity Testing
Anupam Kumar Singh
Real Elements in Algebraic Groups
Amaldev M
Unbounded Data
Kapil Paranajape
The Shlafly Double-Six
12:35 - 13:00
Raj Kumar Pan
The Small-world of Modular Networks
Rajkumar Krishnan
Irrationality of Zeta(3)
Soumya Paul
Potential Games
Nita Sinha
Determination of neutral D meson mixing parameters
Birth of Topological Qubits, a triplet, made visible

Abstracts

03-03-08

Nick Gill    The Thompson groups

The Thompson groups are a type of geometric group that have cropped up in many different places through out mathematics. We look at one type of manifestation of them - as they act on well-known compact sets like the unit interval, and the circle. We look at the problem of classifying conjugacy in the Thompson groups, using some easy geometric techniques.

R Ramanujam    Free and fair e-elections

The 2005 general elections in Estonia were conducted entirely online. If this is an indication of things to come, democratic exercises will soon be entrusted to algorithms implemented in software. It is as yet unclear even what requirements must be met by such algorithms, let alone how to verify that such requirements are met by an implementation. Cryptographic solutions have been proposed, but most are unsatisfactory in some way. We describe some logical problems in this regard.

Arunagiri    Zitterbewegung in Graphene

In graphene, a two-dimensional form of Graphite, electrons behave like massless relativistic particles. With the Dirac theory being natural description, we present in this talk our understanding of Zitterbewegung phenomenon in graphene. Zitterbewegung refers to 'trembling' motion of relativistic particles due to interference of positive and negative energy states. We also briefly mention a couple of other interesting issues as well.

Parameswaran Sankaran    Coarse geometry of groups

Let $G$ be a finitely generated group. Any finite set $S$ of generators induces a metric $l_S$ on $G$ called the word metric. Although the word metric depends on the choice of S, it is an invariant of the coarse geometry' of the group $G$. The study of coarse geometry of finitely generated groups is an active research area. In my talk, the notion of coarse geometry will be made precise and some results and questions will be highlighted.

Praveen M    Reachability problem in Petri nets

Petri net is a mathematical model widely used for modelling systems with concurrent processes. The reachability problem is to find, given an initial state ("marking") of the net and a desired final state ("marking"), whether the final state is reachable. An algorithm for the problem was found by Ernst Mayr, and simplified by Rao Kosaraju, in the 1980's. These algorithms can take arbitrarily large amount of resources (time and/or space). Algorithms with better performance have only been found for subclasses of Petri nets. We see how far a simple approach based on linear algebra can go.

Raj Kumar Pan    The Small-world of Modular Networks

I will describe the "small world" phenomenon and "modular" behavior of a Network. These properties are found to coexist in many real-world networks. I will show this using a simple model and will also discuss how modular structure can emerge in nature.

Abstracts

04-03-08

Amritanshu Prasad    Invariant subspaces for groups of discrete Fourier transform type operators

The Fourier transform is just one of many operators on L2(R) which arise when the standard representation of the Heisenberg group is twisted by an element of the group of 2x2 unimodular matrices. Properly normalised, these operators form what is often called the Weil representation of the metaplectic group. The real numbers themselves are just one of many locally compact abelian groups. To the dismay of realists, mathematical analysts and the more sensible Physicists, I will replace the real numbers by a finite abelian group. Having done this, I will be able to show that the sums of squares of multiplicities of the irreducible invariant subspaces for such a group of operators is the number of orbits of the group on the associated finite phase space.

S Sheerazuddin    Modelling and verification of web services

Web Services are software applications, identified by a URI (Uniform Resource Identifier), that interact with clients and provide some specialized service. In a scenario where there are one or more Web Services along with clients, we would like to verify safety and liveness properties of the composite system. This is a variant of the classic verification problem in Computer Science, which is, essentially, a traversal of state execution graph of the given program. Here, the problem is, a priori the Web Service system has no idea about the number of clients it will service. So, the verification problem is hard as there are infinite number of nodes in the state graph.

Nilanjan    What do we get by "boiling" strings?

We will try to interpret the "limiting temperature" of String Theory, the Hagedorn Temperature, as a phase transition of M(atrix) theory. At this transition temperature the String disintegrates to a cluster of D0 branes.

Rahul Sinha    Anomalies in B meson decays: Can they be signals of New Physics?

We examine whether the discrepancy between observations in B meson decays and corresponding Standard model estimates can be an unambiguous signal of New Physics.

Partha Mukhopadhyay    Noncommutative Polynomial Identity Testing

The polynomial identity testing problem is to check, given a polynomial over a field as an arithmetic circuit, whether it is in fact the zero polynomial. By "noncommutative" we mean that the variables xi do not commute, that is, xi xj is not equal as xj xi. Given as input a circuit C(x1,...,xn) with "gates" for addition and multiplication computing a polynomial f in noncommuting variables over a field, we give an algorithm to check whether the circuit C actually computes the zero polynomial. Our algorithm runs in time which is polynomial in the number of variables, the size of the circuit, the degree of f and the number of monomials in f. Based on this, we also have an algorithm which, given the circuit C, can write out the polynomial f that C is computing. This is joint work with V. Arvind and Srikanth Srinivasan.

Rajkumar Krishnan    Irrationality of Zeta(3)

We will first look at some simple proofs of irrationality of certain numbers and describe the general methods underlying these. We will then look at some proofs of the irrationality of Zeta(3).

Abstracts

05-03-08

Venkatesh Raman    Vertex Cover: Parameterizing Above the Matching Number

Given a road network (of vertices and edges), finding the minimum number of policemen (or petrol bunks) that can be placed at intersections (vertices) such that at either end of each road there is a policeman (or a petrol bunk) is modeled as the well known Vertex Cover Problem. This is a classical NP-hard problem which means that an efficient polynomial time algorithm for the exact answer is unlikely. The variation of the problem, where one is interested in checking whether $k$ vertices cover all edges of the graph on $n$ vertices, has had great success in being amenable for efficient algorithmic approach -- with the existence of an algorithm with runtime $O((1.2)^k + kn)$. This is a practical algorithm whenever $k$ is moderately small, even if $n$ is very large. However, for graphs with a perfect matching ($n/2$ disjoint edges), the answer is trivial (NO) for $k < n/2$, and so the above algorithm becomes impractical when $n$ is large. For such graphs we argue that the more natural question to address is whether the graph has a vertex cover of size at least $k$ more than the size of the maximum matching ($n/2$), and show that even this parameterization has a tractable algorithm as above.

Sridhar    Local Control of Global Chaos in Excitable Media.

Biological excitable systems e.g. the heart, allow propagation of electrical waves which under certain conditions result in spatio-temporal chaos. Such activity is seen in the heart typically following spiral wave breakup and is the reason for life threatening disturbances to the normal cardiac rhythm (also known as fibrillation). Several attempts (mostly unsuccessful) have been made to terminate such chaos using low amplitude control signals applied at a few locations. To enable locally applied control to successfully terminate global chaos, we use a combination of electrical current and alteration of potassium ion channel properties(presumably through the application of pharmaceutical drugs). We show using models of excitable media that this combination can drive a local region from excitable to oscillatory regime, thereby acting as a high frequency source of periodic waves that drive away the turbulence underlying fibrillation.

Veerendra Vickram Awasthi    Homology of Generalized Hawaiian Earring

Eilenberg and Steenrod indicated that Cech homology respects the covering dimension in the sense that if $\dim X = r$ then $H_q(X, Z)=0,\forall q > r$. They asked whether the same thing is true for singular homology? Baratt and Milnor answered it negatively. They produced an example of compact metric space $X$ of dimension $r, r\geq 2$ such that the singular homology groups $H_q(X, Z)$ of this space are non-zero for infinitely many values of $q > r$. Further properties of this space will be investigated and a part of Baratt- Milnor conjecture asserting that $H_q(X, Z)=0$ for $r < q < 2r-1$ will be proved in my talk. An example of a compact connected metric space $Y$ of covering dimension $2r-2, (r > 2)$ will be constructed which has the property that $Y$ is $(r-1)$-connected and $H_q(X, Q)\neq 0 \forall q\geq 2r-2$.

Gautam Menon    Cell division as a pattern formation problem

The division of a single cell is a carefully orchestrated process, involving the formation of large-scale structures containing polymers called microtubules, molecular motors and DNA in the form of chromosomes - the mitotic spindle. It seems possible to model the structures formed when a cell divides in terms of these basic components alone. The crucial question is to understand how large scale,"emergent" spatio-temporal structures (patterns) can form from the interactions of these components. I will describe some recent and somewhat speculative ideas which suggest a possible way in which this problem can be addressed, and some on-going work in this connection.

Anupam Kumar Singh    Real Elements in Algebraic Groups

Let $k$ be a field of characteristic not 2 and $G$ be an algebraic group defined over $k$. An element $t$ in $G(k)$ is called real if there exists $g \in G(k)$ such that $gtg^{-1}=t^{-1}$. An element $t\in G(k)$ is called strongly real if $t=\tau_1\tau_2$ where $\tau_i\in G(k)$ and $\tau_i2=1$. We discuss when a real element is strongly real in $G(k)$ and present the results known for certain groups.

Soumya Paul    Potential Games

A game is a potential game if the incentive of all players to change their strategy can be expressed in one global function, the potential function. The concept was proposed by Dov Monderer and Lloyd Shapley in 1996. The potential function is a useful tool to analyse the equilibrium properties of games, since the incentives of all players are mapped into one function, and the set of pure Nash equilibria can be found by simply locating the local optima of the potential function. We look at such games with various examples and applications.

Abstracts

06-03-08

Kapil Paranjape    What is Reciprocity?

After an introduction to quadratic reciprocity as invented by Gauss, the talk will explain how this can be viewed computationally. This motivates the generalised problem of reciprocity and the solution of it which was proposed by Langlands as a conjecture. We will end with a description of the celebrated result of Wiles and Taylor in this context.

Sitabhra Sinha    Understanding the Mind of a Worm

C. elegans, a worm whose entire nervous system of exactly 302 neurons has been completely mapped, provides an unique opportunity for understanding how behavior emerges from interactions between the neurons in living organisms. To relate the function of the worm nervous system to the collective behavior of its neurons, we have undertaken an analysis of the structural, as well as, dynamical aspects of this neuronal network, using techniques of network physics. Our work tries to address questions such as how did organisms develop centralized information processing (in contrast to a set of semi-isolated stimulus-response pathways) which involved solving complex control problems to achieve very reliable response to stimuli in a noisy environment.

Sunil Simon    Games for distributed systems

Game theory has been widely used in the analysis of protocols and multi agent systems. Typically, turn based games with perfect information is used to model these systems. However, this framework is inadequate to model applications that we encounter on the internet like distributed file servers and distributed caches. Here the agents do not have complete knowledge about the exact global state of the system. The action of the agent therefore, depends on its view of the global state along with certain local conditions. Due to the same reason, the moves are not turn based but rather asynchronous. In this work jointly done with R. Ramanujam (IMSc), we propose a game theoretic framework to model and reason about such systems.

Sujay Ashok    D-branes as Matrix Factorizations

It is by now well understood that string theory is more than just a theory of strings. The theory contains as dynamical objects, a plethora of higher dimensional objects, which appear as solitons from the traditional "stringy" point of view. These higher dimensional objects are referred to as D-branes. In specific highly symmetric examples, I show how these branes can be simply related to factorizations of matrices. This description also turns out to be useful in computing physical quantities of interest.

Amaldev M    Unbounded Data

Computing scientists usually make the assumption of a fixed finite alphabet in which data is made available. When dealing with unbounded data, such as nonces in security protocols, process ids in distributed algorithms, data elements in XML documents etc, it is convenient to relax this assumption. We discuss how this unbounded data-size affects automata and logics.

Nita Sinha    Determination of neutral D meson mixing parameters

Evidence for mixing in the neutral D meson system has recently been reported. We discuss a new method to accurately determine the mass and width differences as well as the CP violating parameters associated with D-anti D mixing.

Abstracts

07-03-08

Venkata Suryanarayana Nemani    Counting Giants

The problem of counting the microstates of black holes in string theory will be reviewed. For a class of (supersymmetric) black holes in the type IIB string theory on $AdS_5 \times S5$, this problem can be mapped to that of counting some (supersymmetric) states, called the giant graviton states, in this theory. Some results in counting these states will be discussed.

N Narayanan    The Discharging Method

The Discharging Method was used to prove the famous planar 4-colour theorem. The method works by showing some local structures are inevitable for a class of graphs and the structures are used to prove results. We have used it to bound the minimum number of colours needed to edge colour some classes of graphs such that any two colours induces a forest. We will present a simple application of the Discharging method and the results we obtained.

Rahul Siddharthan    How DNA evolves, and how to trace its ancestry

I discuss the mechanisms by which DNA evolves. While, in the popular imagination, the driving force for evolution, there are other and more important processes involved, namely duplication and recombination. I then address the computational question of how, given a set of sequences and an evolutionary model, we can determine which nucleotides may have a common ancestry, and which ones may be insertions or deletions. This task ("multiple sequence alignment") has been studied since the 1970s, usually using dynamic programming to optimise alignment scores (edit distances). But most of the attention has been on protein-coding sequence. Existing methods perform poorly or erroneously when applied to non-coding DNA. This is an increasingly important problem, and I discuss some examples from my work. Finally, I touch on some work-in-progress addressing this problem. This will be a pedagogical talk.

Amit Kumar Bhattacharjee    Statics and Kinetics of Nematic liquid crystals

Liquid crystals are objcts which show order in one space direction and disorder in the other. This talk will try to convey you the theoretical framework of the equilibrium properties and the kinetics seen in these objects and will establish the connection of simple and efficient computer experiments, one can implement to study different long-posed problems, on the same time, making contact with experiments.

Kapil Paranajape    The Shlafly Double-Six

The Schlafly double-six is a configuration of six ordered pairs (P_i,Q_i) of skew lines in space such that each P_i meets each Q_j for i and j distinct. This classical construction is known to be related to the lines on a cubic surface. I will give an exposition of this construction and how one can draw a picture of it on the computer.

In quantum computers interacting qubits perform computations. In a topological quantum computer, off springs of interacting qubits called topological qubits perform computations merrily. Their topological character make them ghost like and oblivious to material environment. Quantum computation for them become a merry go round', getting entangled and picking-up non-Abelian Berry phases, without ever loosing their coherence, even in a noisy environment. Kitaev model, a remarkable, non trivial and exactly solvable 2 dimensional quantum spin model exemplifies key ides of topological quantum computation. In our theoretical work on this model [1], birth of a Topological Qubit, from a mother qubit' is made visible. We show that changing the quantum state of one qubit results in the birth of a triplet of topological qubits: an immobile Siamese twin' of pi-fluxes' and a very dynamic Majorana fermion' which frees itself away from the mother qubit and is ever ready for quantum computation, from the time of its birth. [1] G. Baskaran, Saptarshi Mandal and R Shankar, Phys. Rev. Lett., 98, 247201 (2007)