- Manindra Agrawal
On Identity Testing for Depth-4 Circuits
- Somenath Biswas
Recognising insertion languages
Insertion languages are generated by derivation rules of the form xy
--> xzy, x,y,z being finite strings over the alphabet. There will be
a finite number of start strings, and a finite number of insertion
rules as above. The class of insertion languages strictly contains
regular languages, and interestingly, is incomparable with
context-free languages. We describe a polynomial time recognition
algorithm for insertion languages.
- Venkat Chakravarthy
Arthur and Merlin as oracles
Abstract in pdf file
- Anita Das
On tree 3-spanners in 2-sep directed path graphs
Abstract in pdf file
- Subir Ghosh
Approximation algorithms for art gallery problems
In this talk, we present approximation algorithms for
minimum vertex and edge guard problems for polygons with
or without holes. The approximation algorithms partition
the polygonal region into convex components, and
construct sets consisting of these convex components.
Using an approximation algorithm for the minimum
set-covering problem, the solutions for the minimum vertex
and edge guard problems are computed. We discuss a longstanding
open problem on approximation ratio.
- Sathish Govindarajan
On locally gabriel geometric graphs
Let $P$ be a set of $n$ points in the plane. A geometric graph
$G$ on $P$ is said to be locally gabriel if for every edge $(u,v)$
in $G$, the disc with $u$ and $v$ as diameter does not contain
any points of $P$ that are neighbors of $u$ or $v$ in $G$.
The study of this graph is motivated by applications in wireless
networks. An interesting combinatorial question is to bound the
maximum edge complexity of locally gabriel graphs.
We show the following results:
1) For any $n$, there exists locally gabriel graphs with
$\Omega(n^{5/4})$ edges.
2) For points in convex position, we show that any locally
gabriel graph has $O(n\log n)$ edges.
- Pushkar Joglekar
Ajtai-Kumar-Sivakumar sieving method and lattice problems
Given a $k$-dimensional subspace $M\subseteq \R^n$ and a full rank
integer lattice $\L\subseteq \R^n$, the subspace avoiding
problem(SAP), is to find a shortest vector in $\L\setminus M$. It is
not difficult to see that both of the classical lattice problems
viz. SVP(shortest vector problem) and CVP(closest vector problem)
reduces to SAP. We obtain a randomized algorithm to solve SAP treating
$k$ as a parameter, based on Ajtai-Kumar-Sivakumar(AKS) sieving
technique. Using similar techniques we can also get an approximation
algo. for SAP with improved running time. As a consequence of which we
can compute $i^{th}$ successive minima of a lattice in $2^O(n)$ time
if $i$ is $O(n/ \log n)$.
Our algorithms work with respect to any nice gauge function (a
generalized notion of norm). We also prove a $\Omega(2^{O(n)})$
lower bound on the query complexity of AKS kind of algorithms which
accesses gauge function as oracle.
- Johannes Koebler
Are Juntas Learnable in the Parameterized Setting?
We study the parameterized complexity of learning k-juntas and some
variations of juntas. We show the hardness of learning k-juntas and
subclasses of k-juntas in the PAC model by reductions from a
W[2]-complete problem. On the other hand, as a consequence of a more
general result we show that k-juntas are exactly learnable with
improper equivalence queries and access to a W[P] oracle.
This is joint work with V. Arvind and W. Lindner
- Ramesh Krishnamurti
The Capacitated Max-k-Cut Problem
We are given a graph $G=(V,E)$, each edge $e\in E$ has weight $w(e)\ge 0,$
and capacities $c_1,c_2,\dots,c_k.$ The problem is to partition $V$ into
$k$ subsets $V_1, V_2,\dots,V_k$ such that each $|V_i|\le c_i$, and the
sum of the weights of the edges across subsets is maximized. We provide a
simple locally-optimal approximation algorithm with a performance
guarantee of $1-\frac{1}{k},$ improving on the current best guarantee of
$1/2.$
- Piyush Kurur
Fast Integer multiplication using Modular Arithmetic.
We give an $O(N\cdot \log N\cdot 2^{O(\log^*N)})$ algorithm for
multiplying two $N$-bit integers that improves the $O(N\cdot \log
N\cdot \log\log N)$ algorithm by Sch\"{o}nhage-Strassen. Both these
algorithms use modular arithmetic. Recently, F\"{u}rer gave an
$O(N\cdot \log N\cdot 2^{O(\log^*N)})$ algorithm which however uses
arithmetic over complex numbers as opposed to modular arithmetic. In
this paper, we use multivariate polynomial multiplication along with
ideas from F\"{u}rer's algorithm to achieve this improvement in the
modular setting. Our algorithm can also be viewed as a $p$-adic
version of F\"{u}rer's algorithm. Thus, we show that the two seemingly
different approaches to integer multiplication, modular and complex
arithmetic, are similar.
This is joint work with Anindya De, Chandan Saha and Ramprasad
Saptharishi.
Keywords: Integer multiplicaition, Modular algorithms, Fourier
transforms.
- Partha Mukhopadhyay
On Noncommutative Polynomial Identity Testing
Using ideas from automata theory we design a new efficient
(deterministic) identity test for the noncommutative
polynomial identity testing problem (first introduced and studied by
Raz-Shplika and Bogdanov-Wee). More precisely, given as input a
noncommutative circuit $C(x_1,\cdots,x_n)$ computing a polynomial in
$\F\{x_1,\cdots,x_n\}$ of degree $d$ with at most $t$ monomials,
where the variables $x_i$ are noncommuting, we give a deterministic
polynomial identity test that checks if $C\equiv 0$ and runs in time
polynomial in $d, n, |C|$, and $t$.
The same methods works in a black-box setting: Given a noncommuting
black-box polynomial $f\in\F\{x_1,\cdots,x_n\}$ of degree $d$ with
$t$ monomials we can, in fact, reconstruct the entire polynomial $f$
in time polynomial in $n,d$ and $t$
Joint work with V. Arvind and Srikanth Srinivasan.
- N S Narayanaswamy
Some attempts at a better analysis of First-Fit
First-Fit is a very simple algorithm for online interval coloring. In
2004, a new technique for analyzing First-Fit was presented by
Pemmaraju, Raman, and Varadarajan. The result showed that First-Fit
used at most 10 times the optimal number of colors. The new
technique was improved by a few others, including the speaker.
Since 2004, the analysis of First-Fit has been revisited and shown to
use at most 8 times the optimal number of colors. We present our
improvement and other attempts.
- Rolf Niedermeier
Some Recent Trends in Parameterized Algorithmics
- Chandan Saha
Factoring polynomials over finite fields using balance test.
Factoring a univariate polynomial over a finite field is a well known
problem in algebraic computation with important applications in coding
theory. Many randomized polynomial time algorithms are known that
solve the problem efficiently. However, there is no known
deterministic polynomial time solution even under the assumption of
the Extended Riemann Hypothesis (ERH).
In this talk we will discuss an algorithm that factors the input
polynomial in deterministic polynomial time (under ERH) unless the
roots of the polynomial satisfy a strong symmetry condition. The
approach can be used to improve the time complexity of best
deterministic algorithms on most input polynomials. It also yields a
different randomized polynomial time algorithm. The work can be
viewed as an extension of previous work by Evdokimov (1994) and Gao
(1995).
- Saket Saurabh
On Problems Without Polynomial Kernels
Kernelization is a strong and widely-applied technique in the design
of fixed-parameter algorithms. In a nutshell, a kernelization
algorithm is a polynomial-time transformation that transforms any
given parameterized instance to an equivalent instance of the same
problem, with size and parameter bounded by a function of the
parameter in the input. A kernelization algorithm is called a
polynomial kernel if the size and parameter of the output are
polynomially-bounded by the parameter of the input.
In this (survey) talk, we will give recent techniques developed for
proving non existence of polynomial sized kernels for some natural
fixed parameter tractable problems. We will exemplify the approach
with examples of k-path and optimization problems (e.g. Minimum
Dominating Set) parameterized by treewidth.
- L. Sunilchandran
Geometric representations of graphs
A $d$-dimensional box is a Cartesian product of $d$ closed intervals
on the real line. The boxicity of a graph is the minimum dimension
$d$ such that it is representable as the intersection graph of
$d$-dimensional boxes. If the boxes are restricted to be cubes then,
it is called cubicity. I will be presenting some recent (constructive)
upper bounds for cubicity and boxicity.
- Jacobo Toran
Space and width in Resolution
Propositional resolution is, due to its simplicity and its relation to
several automated theorem proving procedures, one of the best studied
propositional proof systems. The most important complexity measure of
a resolutional proof is its size, the number of clauses used. In the
last years, in an effort to better understand this system, other
complexity measures have been introduced. We review in this talk some
of the known results about two of these complexity measures: space and
width. We survey the relationships between these measures and the size
of a resolution proof, mentioning recent results about
characterizations and tradeoffs.
- Kasturi Varadarajan
Clustering to Minimize the Sum of Radii