circuit with threshold gates. Thus,
better understanding of threshold
circuits can lead to better backpropagation algorithms and stronger lower
bound results in learning theory. Indian researchers have already started
designing circuit reconstruction
algorithms.
Isomorphism problems about
structures frequently appear in computer science. Some example structures are NP-hard problems, graphs,
fields, algebras, and polynomials.
Indian theorists have been studying
these closely, and have proved some of
the best results known.
Communication complexity studies the interaction required to solve
a problem when the input is distributed across multiple parties. Indian
researchers, notably at Tata Institute
of Fundamental Research, Mumbai
(TIFR), have made leading contributions to this area.
Logic and automata theory. The
close interplay between automata theory and logic was first identified by Buchi. Pnueli introduced temporal logic
as a language for specifying properties
of reactive systems. Emerson, Clarke,
and Sifakis invented model checking:
determining algorithmically whether a
formal model satisfies a temporal logic
specification.
Reactive systems typically consist of
many interacting components. Viewing the system as a sequential automaton results in the state explosion problem, severely limiting the effectiveness
of model checking. Moreover, temporal logics interpreted over sequences
are forced to reason about an exponential number of equivalent interleavings
for a set of concurrent actions.
Mazurkiewicz proposed enriching alphabets with an independence
relation. Adjacent independent actions commute, creating equivalence
classes of words called traces. Traces
are labeled partial orders of bounded
width and smoothly generalize words
in many respects.
Zielonka defined asynchronous
automata, a distributed model that
precisely captures regular trace languages. This led to a natural question
of model checking asynchronous
automata with respect to temporal
logics defined over traces.
The first temporal logic over
data, as well as in proving non-trivial
lower bounds on query complexity and
space requirements.
Complexity theory. Primality testing has been studied at least since
ancient Greece. However, nontrivial
ideas for testing primes appeared only
in the last two centuries. Apart from
academic interest, primality testing
has gained huge practical importance
because of the need for arithmetic
modulo prime and pseudo-prime
numbers in various cryptographic implementations, error-correcting codes,
and other fundamental computational
problems.
Though randomized polynomial-time algorithms suffice for this
purpose, the basic question of deran-domization remained open till 2002
when the breakthrough result PRIMES
is in P was proved by Agrawal et al.
1
at IIT Kanpur. Agrawal was already a
well-established complexity theorist,
while Kayal and Saxena were graduate students about to start their Ph.D.
thesis work. This paper eventually
appeared in the Annals of Mathematics
and was awarded both the Godel Prize
of EATCS-SIGACT and the Fulkerson
Prize of AMS.
Algebraic complexity theory deals
with the symbolic computation of
formal polynomials in models such as
circuits. The mathematical analysis of
these models involves an interaction
between computer science and algebra
and enriches both fields. The recent
contributions of Indian researchers
at CMI, IIT Bombay, IIT Kanpur, IIT
Madras, Indian Institute of Science,
Bangalore (IISc), IMSc, and Microsoft
Research in this technically challenging area have been stunning, with numerous foundational results and proof
techniques being developed.
Algebraic methods are also used to
show that certain problems are hopelessly hard by proving lower bounds.
For example, the notorious problem
P=NP involves proving an algorithmic
lower bound. There are analogous
lower bound problems for algebraic
circuits. The theory research community in India has been making steady
progress in this area.
Machine learning is a potential
area to apply the insights gained from
algebraic complexity. An artificial
neural network (ANN) is an algebraic
In the 1980s
and 1990s,
theory offered
a unique
opportunity
to keep up with
international
research in
computing despite
limited access
to state-of-the-art
hardware.