Editorial

The Spark wishes its readers a very happy Independence Day! As we celebrate the 75^th anniversary of our nation, the Spark is proud to represent India and IITK, and celebrate our successes along this journey.

We had started out about a year ago, planning a series of theme-based issues to kick-off this magazine. After considerable thought, we drew up a wish list of a dozen stories, hoping for a fifty percent success rate, enough to provide an opening issue on the CSE Programme at IITK. One year and four issues later, we are not quite done. That one issue became two, then four, now going into five. Your support and feedback, especially from the senior professors, have been overwhelming!

This fourth issue continues the CSE story, looking at the early years of the department and the AKS Primality Test, a discovery of great truth and beauty. Special thanks to Professor Somenath Biswas for his help in putting these together. We also include a previously unpublished interview with the late Prof Kesav Nori, conducted by IITK alumnus Shivanand Kanavi. Prof Nori had gained many friends and admirers during his years at IITK, and then at TCS, and this discussion provides insights on his own learnings and shaping influences.

Our campus community has shared two stories for this issue. The first is a review by the students of current construction on the campus, and the second, a photo feature on the beautiful flora during the summer.

And once again, we welcome ideas, comments, and inputs from all members of the IITK community: alumni, students, faculty, and staff, and look forward to hearing from you. You can write to us directly at spark@iitk.ac.in, or post your feedback in our Facebook group 'This Bit of That IITK' We will try to publish as many of your letters as possible.

Letters to the Editors

Graduate Student Memories from those Early Days

Thank you for sharing this. I am truly impressed with the wonderful collection of articles in this edition of SPARK. You have covered a lot of ground giving a historical perspective on the evolution of Computer Science in India. Rajeev Motwani's thoughts on his childhood Interests and shaping Influences are also very inspiring. It has evoked many old and sweet memories.

I had joined IITK in January 1964 in the Ph. D. program in Chemistry. Hari Sahasrabuddhe was my neighbour in Hall 5. At breakfast time, Hari would take all the time to butter a toast making a very uniform layer. It used to be a spectacle, and he would often ask us not to wait for him. Veena was such a divine singer. Once she sang a song for us from the album 'Lata Sings Ghalib' and it mesmerized us.

Besides Hari, I had friends such as Govind Gupta, Surinder Kapoor, and others working in the Computer Centre. These were the early days of computers and there was a lot of excitement about their potential. I often took visitors to the CC and they were always visibly impressed with the sight. For demonstration, a pack of punched cards was kept, that on feeding into the printer produced a large printout of Mona Lisa, which the visitors could take back as a souvenir

Regards,
Sushil Khetan
PhD, Chemistry, 1964-68
Research Chemist, Institute for Green Science, Carnegie Mellon University

Good to hear from you, Sushil. Your memory about Hari buttering toast is quite remarkable; clearly, that procedure was so deeply etched in your memory that you can still recall it vividly. We are tempted to ask him to do it again, with a video recording on YouTube. Short of dragging him back in the Hall 5 mess, it would be a phenomenal good old days memory hack.

Personal Connections!

Thanks for this edition of Spark. This one is really special for me for so many reasons.

TA306 was the first course in which I got an "A". I was fortunate to be taught by both Prof. Mahabala and Prof. Rajaraman. While Prof M taught us Mentor (a pseudo machine language) and Fortran II (not IV) on IBM 1620, Prof R taught Analog Computer programming - he made it so easy to understand.

The Prof Jagdish Lal (Director) that Prof Rajaraman mentions was my father's roommate in Roorkee. Prof Jagdish Lal was the topper of his batch. My father was the first one to enter and last to leave the Students Club as he was more interested in Billiards, Bridge and Tennis than in studies! Prof Jagdish Lal would be fast asleep by the time my father returned from the club. He was very worried about my father and hence every night left notes on his bed for him to study.

The Gautam Bhargava you see in the picture with Rajeev Motwani on page 96 is my cousin brother (Mamaji's son) and the Bumps onlooker, (Sanjay Bhargava on page 106) is his elder brother. Both of them are brilliant. All three of us passed out from Colvin Taluqdars' College, Lucknow and then IIT/K.

So yes, this edition is really special for me. Thanks for sharing.
Regards,
Skand Bhargava
BTech, MME, 1967-72

Thank you Skand! Yes, Sanjay and Gautam are batchmates and good friends of the Editors. So they appear in quite a few photographs, some of which have already been posted in our Facebook group This Bit of That IITK. You should check them out, if you have not seen them already! It is also great to see that the next generation, including Manjul, has maintained contact with IITK (keep reading this issue further)! BTW, we are not sure if Sanjay ever got passed out at IITK, though, despite strenuous attempts to do so. Of course, he did graduate in 1978.

Corrections Appreciated!

Thanks for the new issue of SPARK. Thoroughly enjoyed reading it. I did notice a minor problem: if I recall correctly, MTech in CS was started in 1971 and the first batch graduated in 1973, in which yours truly was one of the graduates along with BK Gairola and Raghavendra Rao among others; the three of us had completed our B.Tech at IITK.
Take care,
Deepak Kapur
BTech, EE 1966-71, MTech CSE, 1971-73
PhD from MIT, Currently a Distinguished Prof. of Computer Science, Univ of New Mexico

Thanks for the revived Spark issues. One correction: The MTech Comp Sci Class of 1975 picture shown in Dr. Rajaraman's article is actually that of the Class of 1978. Thanks,
Ambrish Mathur,
BTech (ChE, 1971-76), MTech (CSE, 1976-78)

Thank you Deepak and Ambrish, the corrections are appreciated! Much of what we publish is anecdotal, dependent on our now fading memories, and names and years have a tendency to get misaligned. Your feedback helps to fit all the pieces together!

Having said that, we have updated the documents on the DORA web archives with your corrections. It does mean that those trying to save copies for themselves need to go back and download the corrected versions of the first three issues!

117

---

Thanks Dinesh! You are referring to Chutki Roy, who was a Hall2/Hall 1 resident. We actually have a listing of most of the Editors, and even a few mug-shots, but are missing a few years, at this time, particularly 1968-70, and then 1985-86. Perhaps our readers can help us fill in the gaps. Meanwhile here is a collage of Spark covers that will take old Sparkies down memory lane. Unfortunately, we have very few issues in our possession, so if you are holding on to any others that are not visible here, we would love to have a copy!

Goosebumps!

Got goosebumps reading the magazine! So many things about the campus I am reminded of - now they have the metro also! How things are changing. And of course, there's Prof Rajeev Motwani's interview. Very beautiful walk down the memory lane in some ways, and of course, a renewed sense of pride in being associated with one of the best technology institutes in the world today. Thank you for sharing.
Regards,
Siddhartha Gupta
B.Tech, EE, 2012

Thank you!

Spark is an excellent initiative which took me back to IITK. Hope it continues for times to come. Loved it!
With best regards
Santanu K. Dutt
BT, EE, 1979-84

118

---

An Afternoon in Silicon Valley

119

---

Oregon State University names Jayathi Murthy its next President

In June, Oregon State University's Board of Trustees voted to confirm Professor Jayathi Murthy as the university's next president. Jayathi got her B. Tech in Mechanical Engineering from IITK in 1979 and earned a Master's degree at Washington State University before completing her Ph.D. in Mechanical Engineering in 1984 at the University of Minnesota. After joining the Dept of Mechanical Engineering at Arizona State University in 1984, she left academia in 1988, to return in 1998, assuming faculty positions at Carnegie-Mellon, Purdue, and Univ of Texas Austin. Since 2016 she has been Dean at the UCLA Samueli School of Engineering, becoming the first woman to hold that position. She established the UCLA Women in Engineering program, which is committed to enabling the full participation, success, and advancement of women in engineering and computer science. She was recognized as a Distinguished Alumna of IITK in 2012, and she was elected as a member of National Academy of Engineering, USA in 2020.

For the friends who knew her at IITK, Jayathi was a balanced and level-headed person but with a gleam in her eye. She didnt waste her time with god's-gift-to-mankind type people, and was very open to activities that included relocating such folks a few rungs down that 'god's-gift'ladder. Likewise, intellectual challenges were her forte, with much time spent in addressing complications arising from divergent solutions to the Navier-Stokes equation or difficult crosswords, after which refreshing bike rides along the Panki Canal with like-minded people were preferred options. Admittedly a reserved personality, she was one you could count upon to be one of the group to get going and do things. In today's management jargon, a great team player. We wish her all the best.

120

---

India to Set-up a New IIT in Jamaica

According to recent news releases, following President Ram Nath Kovind's visit to that country, India will soon set-up its first foreign IIT in the Caribbean island nation of Jamaica. Under the National Education Policy (NEP), India encourages top educational institutes to set-up campuses abroad and Jamaica has shown an interest in having an IIT on their land. The offshore campuses will attract foreign students and build a brand for Indian institutes abroad. They will also expand the exposure of Indian students with international courses and collaborations. Earlier, as part of the India-UAE trade deal, the two nations had agreed to establish an Indian Institute of Technology in the UAE.

Meanwhile, here are some IITK entrance scenarios from the year 2525

121

---

A Brief History of the CSE Department at IITK (1982-2002)

Somenath Biswas (Professor, CSE, 1980-2018)

By 1983, all the original, full-time faculty members of the Interdisciplinary Computer Science Programme had moved on. The Director, Professor S. Sampath, himself took over as the Head of the Department, making a young Asst. Professor * , who had spent only three and a half years as a faculty member, the Associate Head to take care of all day-to-day activities.

There were no labs. The CS Dept didn't have their own computers. Fortunately, the Computer Centre had an excellent DEC-10 system with many interactive terminals, which sufficed. Unix was the Operating platform to use. Uptron, a UP Government organisation, tied up with a US vendor and started marketing Unix boxes. The first server in the CSE lab was the S-32, a Unix server with a Motorola CPU and 6 terminals. It was state-of-the art stuff as far as India was concerned, and it gave a big boost to the academic programme. But support was weak, and it failed frequently. The system got really shaken up when it was taken to Delhi to demonstrate some Indian language software in a Minister's office (after numerous protests by everyone not to do so). The machine failed to work in Delhi and was never the same again. Fortunately, other systems appeared on the market. The software labs took off after that on Unix platforms and the logical culmination of this phase was when the DEC-10 in the Computer Centre was replaced by a set of Unix servers from HP in 1989.

Those early years of the department were tough. Offices in the upper floors of the CC were ad-hoc affairs created by erecting wooden partitions dividing what were labs or class rooms. They were frequently without air-conditioning, and on some nights a civet would mysteriously manage to enter one office or the other, leaving behind her unmistakable offensive stink and worse! Of necessity, each of the faculty members regularly had to teach courses in areas in which they had not specialised. There was an overall resource crunch those days in the Institute, the impact of which was more pronounced on the young Department as it had hardly any sponsored projects or any other source of funding.

* Editorial Note: The young Assistant Professor was Somenath Biswas.

122

---

Despite all the hardships, the young faculty members were a happy lot, they worked together to set up labs, recruit and train engineers, devise curricula, and set up the academic ambience. They would have long faculty meetings, arguing with each other with gusto and yet, finally, they would somehow reach decisions to everyone's satisfaction. There were absolutely no ego clashes. This happened, possibly, because each had found space to grow, and each felt himself to be an equal partner in the task of building the Department. Another very positive factor was the quality of the students around them; the young faculty were constantly trying to overreach: they would try out new elective courses to learn new areas, they would offer, in retrospect, very challenging B.Tech and M.Tech projects, would set brilliant but extremely difficult exam papers, but the students took all this happily, more as partners than as pupils. The support from the both B.Tech and M.Tech students was crucial to the successes that were achieved. Everyone worked together as a family to move things forward.

The 1990s

By the time the 1990s began, the Department had a settled look. The faculty strength was up to fifteen. including several of the Department's own alumni. There were now faculty members in all core areas of CS. Email had arrived, and the Department now saw more academic visitors. During 1995-96, two people who had contributed immensely in the early years of the Department, Gautam Barua and Rajeev Sangal, left IITK. Barua had built the lab facility, initiated work on the Unix kernel, and introduced the era of networking. Sangal had created a group in natural language technologies, brought the linguistics area of the HSS Department into close contact with the CS Department as a result of which regular teaching in computational linguistics would be offered.

123

---

In the mid-1990s it became evident to the department that if it was to grow, outside projects would be necessary to generate some resources on its own. When Cadence Design Systems made a proposal to conduct Cadence's induction training programme, the Department readily agreed. The results pleasantly surprised everyone – not only was the deadline met but the quality of the modules also turned out to be very high. An additional bonus was the fun of all working together! The Department ran the project for three successive years, from 1995 to 1998.

This success became widely known and IBM in 1997 came with a proposal of far greater scope. Those days, the supply for trained manpower in CS fell greatly short of the demand. IBM decided to set up IBM Accredited Centres for Education (IBM ACE) all over the country as well as in some selected locations abroad. The goal was to offer intensive training in core areas of CS. IBM approached the Department with a comprehensive proposal to frame the overall curriculum, create the course modules, and conduct a number of training programmes for ACE instructors. The Department agreed. The task this time was harder because the course modules for ACE had to strictly adhere to the well-established norms and standards of IBM's own in-house training programmes. The quality of the modules was so good that IBM Worldwide added these to their repository in 1999, which provided further royalty earnings for the Department. For both the Cadence and the IBM projects, Sanjeev Aggarwal, a relatively younger faculty member with outstanding leadership skills, coordinated and managed to coerce/persuade the rest of the faculty members to do their tasks within the deadlines that he would be setting from time to time.

124

---

Endowed chairs, Department building, PRIMES in P

Pankaj Jalote, then a faculty member, spent two years, 1996-98, at Infosys. He got to know Mr. Narayana Murthy, the charismatic leader of Infosys, and his wife, Mrs. Sudha Murthy quite well. The Murthys were keen to do something for the institute, one reason being that Mr. Murthy was an alumnus, and had done his MTech at IITK. They expressed their desire to set up an Endowed Chair in the Department, an idea they had already discussed with Jalote. They donated some of their personal shares in Infosys, valued at Rs. 65 Lakhs, and with this as the corpus, the Department got its first Endowed Chair which was named after Mr. Murthy's father, Mr. N Rama Rao. Arvind (of MIT and an alumnus of IITK), a leading figure in the area of computer architecture, was the first occupant of the Chair. The endowment also created and operated an innovative plan for inviting distinguished scholars for short visits making use of the interest earnings of the corpus for the period when the Chair was unoccupied.

Mr. Murthy later decided to donate a further sum of Rs. 2.5 crores to IITK for a project which normally would not be funded through Government sources. The Institute prepared a list of possible projects, one of which was for a Departmental building. Mr. Murthy decided to support this project, and soon found that the cost of a proper building would far exceed Rs 2.5 crores, and he donated another Rs. 5 crores. Faculty members of the Department had endless discussions amongst themselves as well as with the architect on every detail of the proposed building. When completed, it turned out to be one of the best buildings in IITK, both aesthetically and functionally, and managed to capture a sense of openness and friendliness that is rarely found in public buildings. History needs to record the enthusiasm, zeal, and sheer hard work that Pankaj Jalote, then the Head of the Department, had brought to bear on this project.

The Department was very keen to name the building after Mr. Narayana Murthy, but he did refuse, and asked that it be named after a person of learning and teaching. IITK, therefore, decided to name the building after the Late Sri HR Kadim Dewan, father-in-law of Mr. Murthy, who had been a teacher all through his adult life.

125

---

During 2001-02, the Department received two more instances of generous support from IITK alumni. Prabhu Goel contributed towards the setting up of the second Endowed Chair in the Department, and also for a centre within the Department for research in computer security. Rao Remala, one of the lead developers of the original Microsoft Windows, who had obtained his MTech in CS in the 1970s , contributed US$ 100,000. It was decided to use his contribution to support conference travel for PhD students. This was the first corpus, perhaps anywhere in the IITs, which made travel support and international exposure possible for PhD students.

The new Departmental building was inaugurated on a typical Kanpur foggy winter morning, on 3 January, 2002. The Department celebrated the inauguration with a two-day workshop on Current Practice and Future Challenges in Computer Science with a number of distinguished speakers including Mr. Murthy.

However, a celebration of an unsurpassable nature came about on 4 August 2002, when the world got to know that Dr. Manindra Agrawal, a young Professor of the Department, along with his two undergraduate students Neeraj Kayal and Nitin Saxena, had discovered a deterministic polynomial time algorithm to test if a given number is a prime or not. This discovery resolved one of the most profound open questions of mathematics and computer science, a question that was first raised at the time of Eratosthenes. The discovery was reported on the front page of The New York Times on 8 August 2002, and by the media all over the world soon thereafter. Along with the names of Agrawal, Kayal and Saxena, the names of IITK and its Department of Computer Science were now associated with a discovery of great significance, elegance, and beauty. What a dream start to the new millennium for the Department!

Acknowledgements: I thank Professors V. Rajaraman, Gautam Barua and Pankaj Jalote for the information they provided to me. Of course, only I bear the responsibility for all the inaccuracies and omissions the article contains.

126

---

About the author:

Prof. Somenath Biswas was born at Chittaranjan, West Bengal, in 1952. He completed his early schooling at Chittaranjan, and then obtained his B.Tech (Electronics and Electrical Communication Engg.) from IIT Kharagpur in 1973, and his M.Tech and Ph.D in Computer Science, in 1976 and 1980 respectively, both from IIT Kanpur. He joined the faculty of the Computer Science and Engineering Department of IIT Kanpur in 1980, where he was the Sanjay and Rachna Pradhan Chaired Professor. He has been the Department Head (1986-87, and 1995-97), and the Dean, Faculty Affairs (2005-07). IIT Kanpur recognized him as an Institute Fellow for his contributions to the institute in 2018.

Prof Biswas is a Fellow of the National Academy of Sciences, India. He has been a Visiting Professor at Aarhus University (1989) and at the University of Nebraska, Lincoln (1999). He has helped set up the Computer Science programme at IIT Goa and served as Director of IIIT Allahabad. He has been the President of the Indian Association for Research in Computing Science (2000-2002). His research interests include computational complexity theory, randomised algorithms, computational biology and logic in computer science, and his PhD students have included Prof Manindra Agrawal.

127

---

From the New York Times

August 8, 2002

New Method Said to Solve a Key Problem in Math

By Sara Robinson

Three Indian computer scientists have solved a longstanding mathematics problem by devising a way for a computer to tell quickly and definitively whether a number is prime -- that is, whether it is evenly divisible only by itself and 1.

Prime numbers play a crucial role in cryptography, so devising fast ways to identify them is important. Current computer recipes, or algorithms, are fast, but have a small chance of giving either a wrong answer or no answer at all. The new algorithm -- by Manindra Agrawal, Neeraj Kayal and Nitin Saxena of the Indian Institute of Technology in Kanpur -- guarantees a correct and timely answer. Though their paper has not been published yet, they have distributed it to leading mathematicians, who expressed excitement at the finding.

''This was one of the big unsolved problems in theoretical computer science and computational number theory,'' said Shafi Goldwasser, a professor of computer science at the Massachusetts Institute of Technology and the Weizmann Institute of Science in Israel. ''It's the best result I've heard in over 10 years.'' For mathematicians and computer scientists, the new algorithm represents a great achievement because, they said, it simply and elegantly solves a problem that has challenged many of the best minds in the field for decades.

Asked why he had the courage to work on a problem that had stymied so many, Dr. Agrawal replied in an e-mail message: ''Ours was a completely new and unexplored approach. Consequently, it gave us hope that we might succeed.''

Methods for determining whether a number is prime have captivated mathematicians since ancient times because understanding prime numbers is the key to solving many important mathematical problems. More recently, attention has focused on tests that run efficiently on a computer, because such tests are part of the underlying mathematics of several widely used systems for encrypting data on computers and securing transactions over the Internet.

On Sunday, the researchers e-mailed a draft of the paper on the result to dozens of expert mathematicians and computer scientists. Dr. Carl Pomerance, a mathematician at Bell Labs, said he received the paper on Monday morning and determined it was correct. After discussing the draft with colleagues over lunch, Dr. Pomerance arranged an impromptu seminar on the result that afternoon.

This article appeared in print on Section A, Page 20 of the New York Times National Edition of August 8, 2002, and can be accessed in its entirety here: method-said-to-solve-key-problem-in-math.html (access may require a subscription).

It is also available at Sara Robinson's home page at: https://www.msri.org/people/members/sara/
The image of the NY Times headquarters is from Wikimedia Commons.

128

---

PRIMES is in P: the Story of a Discovery

Professors Manindra Agrawal, Somenath Biswas and Nitin Saxena of the IITK CSE Department contributed to this article. It uses extracts from a paper entitled 'Story of a Discovery' by Somenath Biswas which gives the details of the sequence of ideas and insights which culminated in the discovery discussed here. This paper is available in the IITK CSE archives. A copy of this paper can also be downloaded from the Files section of the Facebook group 'This Bit of That IITK'.

The pictures in this story are from the IITK CSE Dept archives.

August 2002: End of a Quest

On 4 August 2002, a short e-mail message reached the mailboxes of a small group of mathematicians and theoretical computer scientists; the message simply asked for comments on an attached draft paper claiming to provide a deterministic polynomial time algorithm to determine if a number, given as input to the algorithm, is prime or not. The day being a Sunday, the message remained unread in most of the mailboxes. One mathematician from Holland Heinrich W Lenstra, Jr. (who was then at Berkeley), did see the message which had come from Manindra Agrawal, whose name was familiar to the computer scientist recipients of the e-mail, but not to the mathematicians.

Lenstra, a leading computational number theorist, was quite used to getting solutions of long-standing open problems of number theory from all kinds of people round the globe, because number theory is an area that fascinates people in general, and whose many celebrated open problems can be stated in the language of school mathematics. Lenstra must have suspected that the email was from some naive enthusiast, and yet he could not resist the temptation of having a peek at the attached draft paper because it was about a problem that he himself had struggled with for more than two decades.

Even a cursory glance at the paper was enough to see that it was mathematically mature. The paper had a very original approach and did not use any of the sophisticated mathematical toolkits whose use is almost mandatory in modern day number theory. The paper was short, the proposed decision algorithm was only thirteen lines, and the correctness proof of the algorithm, the crux of the paper, was detailed in less than three pages. The proof rested on six lemmas, and if their proofs were indeed correct, then it was a great breakthrough. Lenstra phoned Manjul Bhargava (a brilliant young researcher who would go on to win the Fields Medal in 2014), and together they went rigorously through every detail of the paper, sitting in a Berkeley cafe. Finally, after several hours and many cups of coffee, the two were fully convinced that not only was the paper correct in every detail, but also that it was a gem of a mathematical discovery.

The next day, Lenstra distributed the paper to some of his fellow researchers; one of them, Carl Pomerance contacted Sara Robinson, the science correspondent of The New York Times, informing her of the great breakthrough. She contacted Manindra Agrawal and filed her report after several email exchanges. The August 8 issue of The New York Times carried prominently on its front page this headline: New Method Said to Solve Key Problem in Math Soon, all major newspapers around the world also carried the news, making Manindra Agrawal, Neeraj Kayal and Nitin Saxena, the three authors of the draft paper, mathematical celebrities.

129

---

Curiously, it was accidental that this great result came about in that summer of 2002, as none of them had planned to stay back for the summer in Kanpur that year to work together on the problem. Manindra, already a full Professor in the Department of Computer Science at IIT Kanpur, would turn thirty-six in August 2002. Neeraj and Nitin had just completed their undergraduate programme in Computer Science in the beginning of May and were in their early twenties. Manindra had been working on primality testing way back from 1998, sometimes with another colleague or with undergraduate students, but often on his own. Although unaware of it, Manindra had already discovered many of the ingredients of the celebrated result by 2001. Neeraj and Nitin in their BTech project with Manindra as the advisor, had examined certain aspects of the problem, and they had, by the summer of 2002, a very good grasp of the conceptual apparatus the three would finally use.

In May 2002, when Manindra, Neeraj and Nitin decided to do some more work on the problem, none of them had any clue that the end was so near. It was by chance that all three were staying back in Kanpur that summer. Manindra was supposed to be in Germany, but at the last minute he cancelled the trip, reluctant to leave behind his wife with two small children. Nitin was expecting a scholarship to study abroad, which somehow did not materialise. Neeraj was supposed to be at TIFR (Mumbai) that summer to join the PhD programme there, but personal concerns led to postponing his move.

Perhaps more to take their minds off their disappointments than anything else, Manindra suggested to Neeraj and Nitin that all three together take another look at the primality problem. Suddenly, familiar facts started tumbling into new places and they could sense that something was emerging. In the second week of July, the final idea came to Manindra as he was taking his little daughter to her school. Right then, on his scooter ambling down a quiet IITK road, Manindra knew that they had the final piece of the jigsaw puzzle, solving a problem that had been open since the time of Eratosthenes.

130

---

The Challenge: Decision Problem for Primes

Primes are integers (>1) divisible only by 1 and themselves. Every natural number other than 1 is the product of a unique set of primes, e.g., 24 is the product of 2, 2, 2, and 3, but not any other set of primes. What we seek is an efficient algorithm that decides whether an input number is prime; a brute- force algorithm (which successively attempts to divide the input by each smaller number) takes too much time. Computational complexity theorists have a definition of what "efficient" could mean: if it takes n bits to represent a number, what is the maximum number of steps needed by the algorithm, as a function of n? Efficient algorithms are polynomial time, i.e., the computational time needed is no worse than a polynomial function of the number of bits. For example, well-known sorting algorithms have sub- quadratic complexity: if the number of elements to be sorted increases ten-fold, the number of steps needed increases by a factor less than 100.

The brute force algorithm for detecting primality is inefficient because the number of computational steps needed is exponential (not polynomial) in the number of bits representing the number: for 100- digit numbers using a computer that executes a million elementary steps/second, 10¹² centuries would be needed! But only a second would be needed if a primality decision algorithm exists that takes at most (logn) ³ steps for any number n. So, the challenge is: to devise a polynomial time algorithm to decide primality.

Pratt showed in 1975 that for every prime p, there exists a short and easily verifiable proof that p is indeed a prime. Miller's 1976 result showed that primality testing can be done in polynomial time if the Extended Riemann Hypothesis is true- but this hypothesis is unproven. Randomised algorithms were devised by Solovay and Strassen (1977), and Rabin (1980), but carry a small probability of error. The goal of a truly polynomial time algorithm remained elusive, in spite of extensive efforts by some of the best minds.

131

---

132

---

133

---

Truth and Beauty

The work of Manindra, Neeraj and Nitin has been hailed as one of great elegance and beauty. They use familiar mathematical objects in an unfamiliar manner, they use facts and attributes that were previously regarded as reasons for difficulty in bringing about clarity. They make use of a small prime to unlock the primality question of a large candidate number. Till then people had found primes which are smooth to be easier to handle, but they make essential use of the very non-smoothness of one prime to decide the primality of the input number. Indeed, the paper of Manindra, Neeraj and Nitin is a work of beauty in the same sense that many great results are considered beautiful.
In 2002, soon after the discovery was made, Manindra was asked by a media person, What made you keep on looking for a deterministic polynomial time algorithm for primality testing in spite of knowing that the problem was so hard? Manindra's reply was that because he had an approach which no one had tried before, he felt that it was worth pursuing. Later, he confided in someone that that had been only half the answer-the other half was that he knew that the approach would succeed.
Perhaps such knowledge and the resultant conviction can come only from an awareness of truth not in the ordinary sense of the word, but as that which is what the voice within tells you. However, there are also voices without, and they tell us to be prudent, to be careful, not to waste time in running after that which could very well turn out to be a mere chimera. How can one ignore these voices and remain steadfast to the voice within? The reason perhaps is that simultaneously the eye within sees something of great beauty. Manindra found something so attractive in the condition (2) that he just could not ignore it, he kept coming back again and again to it in spite of many and repeated disappointments. The voyage of discovery is often long and painful, but what guides the voyage is perhaps the perception of truth and what sustains the voyage is a vision of beauty. Ours is a blessed existence because some amongst us sometimes are capable of perceiving truth and beauty.

About Prof. Manindra Agrawal

Manindra Agrawal got his B Tech and PhD in Computer Science (CS) from IIT Kanpur in 1986 and 1991, respectively. He has been a faculty member at IITK since 1996, where he is currently Project Director of the Technology Innovation Hub in Cybersecurity and Professor in the Department of Computer Science and Engineering. He has served as Head, Department of CSE, 2006-10, Dean of Resource Planning and Generation, 2011-12, Dean of Faculty Affairs, 2013-15, and Deputy Director, 2017-19. Manindra has been widely recognized for his pioneering research in CS. He is the recipient of the first Infosys Prize for Mathematics in 2008; the Clay Research Award in 2002; the Godel and Fulkerson Prizes for theoretical advancements in CS in 2006; and the Shanti Swarup Bhatnagar Award in Mathematical Sciences in 2003. He has been honoured with Padma Shri in 2013. He is a Foreign Associate of the National Academy of Sciences (US), and fellow of all Indian Science and Engineering Academies.

Manindra started his research with a recursion theoretic approach to complexity theory. An important unproven conjecture from the 1970s was that the hardest sets in the class NP are all isomorphic under polynomial time reductions; over a decade (late-80s to late-90s), through a series of papers, Manindra proved this result for the case when instead of polynomial time reductions, one considers a stronger type of reductions, called first-order reductions, encompassing nearly all known hardest sets in NP. The other major theme of his work has been to find a polynomial time algorithm for the Polynomial Identity Testing (PIT) problem. An exploration of special cases of PIT problems led to a deterministic polynomial time algorithm for Primality Testing. He also showed that if one can solve PIT for a very special class of polynomials, the solution can be extended to all of PIT; currently, he continues to investigate this special class of polynomials.

134

---

In 2021, he created a model called SUTRA for capturing the trajectories of coronavirus transmission across the world, successfully addressing two challenges faced by existing models: interventions made by governments as well as the non-detection of a large number of asymptomatic patients.

135

---

Prof Kesav Nori: In His Own Words

From an Interview with Shivanand Kanavi

Shivanand Kanavi:  Tell us about your early childhood and schooling

Kesav Nori:     I was born in Nasik in 1945 Dec.... I went to a convent school in Baroda and came here [Bombay] and joined Xavier's in the fifth standard. When I finished 11th standard from Xavier's in 1961, my father felt that if I went back to Xavier's I would not be pushing myself because there will be all old friends around me, and he felt I should put more effort, so I went to Jai Hind college here which has always been known to be exam conscious. Therefore, I finished my Intermediate Science from here and appeared for the IIT entrance exam.

Shiva:     Tell me a bit about your father, firstly why did you have to move from Nasik to Baroda, and Bombay.

Nori:     We had to move because my father was in the government service. He had joined the Indian Services of Engineers cadre in 1930 and was deputed to the Presidency (Government) of Bombay.

Shiva:      And what kind of job was he supposed to do?

Nori:     He was an engineer. He was for some time working in roads and buildings, and most of the time in irrigation and power. So, he was the superintending engineer of the Gujarat irrigation circle when we were there, and in fact that was the longest stint in his career at that time in one place. All my elder brothers studied with my uncle in my native place in Bapatla, in Krishna district (south of Vijayawada) because my father was being transferred around considerably. I think between Nasik 1945-1948 when we moved to Baroda, he must have been transferred five or six times, so very small stints at each place.

Shiva:     You are the youngest?

Nori:     No, I have one younger brother who was born in Baroda... a mathematician, his name is Madhav Nori, and he is at the University of Chicago.

136

---

Shiva:     Before your father everybody else in the family were engineers or in the scientific profession?

Nori:     My grandfather was a lawyer in the high court in that region (Andhra). But he stopped working with the British courts during the Quit India movement.

Every holiday we traveled from Bombay to Koyna via Pune. We would find all the NDA (National Defence Academy) people standing straight and I would slouch, and my father would say: look how smart they are, do not slouch, do something it will improve you in life. So, I appeared for the exam and being a little naughty, I said that if selected I would join air force, knowing fully that I had glasses and would be rejected. But as it turned out I had a very high rank.

So, I just appeared for this IIT exam and happened to make it, so I went in. I studied in IIT Bombay from 2nd year to the 5th year and passed out in 1967. I did not want to join the industry at the end of B.Tech. My father said in that case you have all your books, why don't you read some of them, I am sure you would have missed learning some of them for whatever reason, figure out whether you like something more and then pursue it.

When he said, "read books, take a year off, and find out what you want", I said it is better to do an M.Tech. and get some scholarship at least. I wanted to have at least some independence. I joined Kanpur and my first one year was miserable because all the electrical engineering subjects which I found difficult in B.Tech. were up there in the Master's program. But learning to program, computing was a joy. Systems engineering was nice, integrated and abstract and you did not really have to know how much current is going through.

In Kanpur, Profs V Rajaraman and C N Mahabala were the only two people teaching computer engineering and H Kesavan had taught assembly language and programming to the previous batch. But he had started his Systems Engineering course since then and I went through those courses. After doing these systems engineering classes when I went into my second year I was just taking courses and suddenly within the last 7-8 months I felt that I am going to graduate again and I don't know what I want. That really shook me up. That is the first time I sincerely started studying for myself.

I joined Kanpur in July and became an RA, SRA, in the computer center. There was no immediate need to graduate and get kicked out, so it helped me and gave me more time to learn computing and I submitted my thesis a year later. When Narayan Murthy was doing his thesis, he was working with Hari Sahasrabuddhe, and I was the interpreter for them in some ways.

I had started on one project which was a very popular project of those times -- building a calculator, and I did the entire system design. In fact, I re-did it because there were two students before me who had worked on that project and did bits and pieces. This was my MTech thesis. When I started putting the circuitry for the calculator based on the first thesis, I found the display parts and all were organized and the main calculator itself was lines going up one page into some other page somewhere but the circuit itself was blank. They were not shown. What I did was to fill in all the systems design, details of all the circuits, put them on a huge sheet, and then took it to Rajaraman and showed it to him.

The size of the calculator would have been approximately the size of a laptop with extensions and so on, or not a monitor, but an LCD monitor may be, with a little hub to show the display. I did not have the guts to work with hardware in the laboratory because I had very little experience. So, I went back to Rajaraman and I said, this is what they did, and this is what I have done so far, and now you have a complete design which will work.

137

---

I told him I wanted to move to another project. Then he gave me a problem which none of his other students would take. How do you know whether one computer is better than another? Is 1401 any better than 1620? If they are the same kind of computers and you are looking at different models that may be easy. But they are different architectures altogether. When you compare computers, can you compare the implementation of programming languages and say that is a part of the computer. I had seen several PhD theses, from MIT, from Ann Arbor (Michigan). These two places were working very heavily in this area. I looked at a lot of PhD theses there and tried to understand them and proposed various things.

I would say at this point I have three choices, and Rajaraman would say why don't you try and come back with some assessment and so on and this went on for some time... I kept doing more and more of this till one day Mutthu (Prof C R Muthu Krishnan, who was doing his Ph D in CS then) said you are an ass, just get out and write up the thesis. I said what do I write, and he said write about all the things you have done.

So, I wrote the whole thesis and submitted it. For the exam Mahabala came back, he had been in MIT that year. He sat in the exam and asked a lot of questions. He said why didn't you spend six months more you could have got your PhD instead. That was the first shock I received in my life when I understood I could do research.

I was wondering what next when Prof R Narasimhan happened to visit IIT Kanpur. He had a long chat with me and suddenly he asked a question: would you like to come to TIFR? They were just beginning on the Aegis program there. It was an early warning system. This was a ground-based system and there was a project given to TIFR to build one of these things based on PDP 11 architecture. I worked in Aegis in TIFR from end of 1970 for the first 3 years. I worked on the hardware architecture because ECIL was supposed to make them but they did not want an exact copy but they

138

---

wanted to make sure that they could develop everything on a PDP 11 and later on translate it to machine language or TDC 316 and use it.

We had to actually make the computer in India, and I was in that part of the strategy and technical work. The question was: how do you make a TDC 316, which was different from PDP 11 but can be mechanically managed. PDP 11 was a modular and a very structured machine, very easy to understand even at the machine language level. It had a simple cleanly structured bus so if you wanted to extend the machine, there was a standardized structure on the bus interface, which would allow you to indefinitely expand. So, the architecture was very nice and simple.

Shiva:     But all the hardware part of it the cards that you needed, memory, etc., were they available off the shelf or did you have to make it yourself?

Nori:     I think they were available, but because defence would have to import it, you never know there may be a ban. What the defence people did at that time was that they put out a tender requirement and several companies from Europe bid for the entire system all the components and so on. Of course, they were expensive and all of them decided to use the PDP 11 so that is why system design choice was limited.

I did all the computer design: operating system design, Compiler design and implementing a compiler and an assembler; all that we did in those years. After three years of this I moved out of AEGIS and came back under Narasimhan. That was the time when NCST (National Centre for Software Technology) was being formed around 1973-74. So, I started working towards my PhD in IIT Bombay and progressed to a point where I should have been ready to finish but it got stretched.

In 1973, there was a winter school in Bangalore organized by TIFR, and the lecturer was [David] Gries from Cornell. He came and talked about compiling, he also talked on the side about structured programming, and accidentally I was involved in trying to apply structured programming to compiling.

I went to Zurich in 1974 and met many of the well-known people in computing. I had good fortune of working with [Niklaus] Wirth, and later by April of 1974, there was a meeting in Zurich in which [Edsger] Dijkstra, [Tony] Hoare and all these people had come. Hoare was the one who asked me: what are you doing and at which University are you in the US, and so on. So, I said, I am from India and I am working in TIFR. He was a bit curious to know what happens and what problems interested me. So I said compiler correctness and so on.

Initially he must have thought I was daft because I was claiming seemingly very big things about compiler correctness. I did not know whether it was big or small or difficult, it was interesting, I was doing something. And I felt I had the problem under control. And he was surprised to hear such a thing. So he tried to find out more and more. My method of explanation was not smooth or clear, as it should be, at least now I can say it. He helped me; in fact, he spent a lot of time with me in straightening my head. I was feeling even better because somebody from outside felt that my research was reasonable.

Dijkstra was the first to introduce the need for discipline when programming because you are using no materials, only your head while creating the program. But how do you know you are using it well or you are not delivering a bug instead of a correct program. So he wrote lucidly but abstractly, about programming and how we could write them, so that it would work well. In that sense, he was very important.

139

---

In 1975, I went from NCST to [Digital Equipment Corporation's factory, to their integration center in Marlborough. It is about 40 miles from Boston. And then we started getting into the plans for research in NCST and I got into that. Finally, by 1977, I had completed the work: how to prove, what is the nature of the proof, what are the details and I was also at that time documenting the course that we had done. I went to DEC just to know about the systems so we can come and implement it here. This came in handy later when I joined IITK as faculty in the newly formed Department of CSE and the computer centre had acquired a DEC-10.

Epilogue:

From IITK Prof Nori would go on to Carnegie Mellon University, returning to India in 1983, to join TRDDC, leading the institution later as Executive Director. At TRDDC, his major contribution was bringing rigour into the programming process. He assisted in developing software tools that greatly simplified correcting the Y2K bug in COBOL programs, enabling TCS to complete these projects economically and in record time.

The late Rajeev Motwani had talked extensively about Prof. Nori in his discussions with Shivanand Kanavi (see the Spark Diaries #3, pages 99-100). In Rajeev's words,"That was the wonderful thing about Nori who was a very inspiring person. He did more than just teaching. He created such a wonderful ecosystem and developed a personal connection with his students".

About Shivanand Kanavi:

Diamond Jubilee Academic Complex

The New Core Labs (NCL) 2.0, as we called it two years back, was under construction for the last three years. Its name was revealed during its inauguration (on 20th April by Dr. Radhakrishnan, Chairperson, BoG, IITK). The Rs. 109 crore cost of the building justifies its size-a massive carpeted area of 35,000 square meters, (which is roughly the same as 5 football fields). It is now the largest academic building on campus and the purpose of a lot of the rooms hasn't been decided yet! The building is five storeys high, and will have labs for UGs and PGs, lecture halls, and will also function as the department building for the Department of Design and the Department of Sustainable Energy Engineering.

141

---

Science and Technology (S&T) Building

In between the NCL and the Flight Lab, construction of the Science & Technology Building is in progress. Construction started in October 2020; and was expected to be completed this past winter. However, COVID and lockdowns frequently halted work, and this 5-story building is now expected to be ready with all amenities by Diwali 2022. The project costs a little over 58 crores which includes BMS, utilities, lifts, fire alarms, and PA systems.

Research Lab Complex

Adjacent to the site of the S&T Building, another building is under construction. Yes, you guessed it right, another research building! This one, called the Research Lab Complex, has been under construction since April 2021 and is slated for completion by early 2023. The project cost is estimated to be under Rs. 75 crores, including amenities like plumbing, sewage system, electrical works, fire alarms, lift, PA system, and a Building Management System (BMS) for centralized management of the infrastructure. Three floors have been constructed by March 2022. If the current pace of construction isn't disrupted, we'll surely have many more research labs by the turn of the year.

142

---

Earth Science Labs Building

As we proceed from the Techno Park Building towards the Flight Lab, we come across a towering 7-floor construction nearing completion. This building is the Earth Science Labs Building. It has been under construction for the last 3 years, but due to COVID slowdowns, the work is not yet complete. The fully furnished building is expected to be handed over to the institute in the next 2-3 months. The project cost is estimated to be nearly Rs. 19.7 Crore.

143

---

Aerospace Department Building

Across the road from the IME building, we have the Aerospace Department building that is nearing completion, and by the time this article is published, it will be close to handover to the institute. It is a 7-storey building, along with a basement. As with other construction projects, COVID delays affected this building which was originally to be completed by the end of 2020. At handover, after the completion of all utilities, firefighting systems, CCTV systems, etc., its cost will come to just below Rs. 58 crores.

Core Labs Extension

Well, you can't call every new lab building "New Core Labs", right? This one is called Core Labs Extension. Adjacent to the Materials Sciences Labs, ACES building, and the DoAA Canteen, the construction on this site was originally projected to end in April 2020. Of the listed buildings not yet inaugurated, this would probably be the first. This building will provide more labs, mostly for the core departments such as MSE, CHE, CHM, etc. The construction is of 4 floors, including ground, and its estimated cost is about 10 crore rupees.

Faculty Building Annexe

That large building you see being built from the porch of CCD, or the skywalk near the Library is the Faculty Building Annexe. This building will provide for the new offices of the administrative faculty: The Director, Deputy Director, most of the Deans, and various other professors. Construction started while most of us were at our homes, and it has been rapid-the fully-functional building will be handed over to the institute tentatively before the end of this year. The cost of the 6-floor annexe is roughly Rs. 31 crores.

144

---

Hall 14

We also have a new hostel coming up! The location of Hall 14 lies beyond Hall 13, on the diagonal road. Although we do not know much about the contract, the buildings are supposed to be handed over by January 2023, though delays might shift the deadline to the end of the second semester of 2022-23.

Also, just like Hall 13 with A-B-C blocks being functional even before the blocks D-E-F were fully constructed, there's a possibility that Hall 14 would also be built in parts, with one-half being functional before 2023. Well, aren't we excited!

Reporting and text by: Sanika Gumaste, Ayush Anand, and Bhavya Sikarwar
Design by: Vijay Bharadwaj
Edited by: Devansh Parmar
Vox Populi, May 2022

145

---

The Summer Campus

The peak of Summer brings a blooming campus! A time when IITK turns into brilliant shades of yellow, pink, and orange from the Amaltas, Gulmohars, and Bougainvillaeas. We reached out to members of our FaceBook group to see how it looks today. And here are some images that they shared!

146

---

Left: The bougainvillaea tree between the FB and Western Labs has grown considerably over the years and now reaches over the upper deck of the walkway. Picture Credit: Guntas Singh Brar (BT, CSE, 2018-22). Right: A student (Yuvraj Singh, BT, CE, 2020-24) makes his way up the ramp to the walkway near the Library. Picture Credit: Granth Choudhary (BT, EE, 2020-24)

147

---

Left: A lone cyclist makes his way from the Library towards the FB. Picture Credit: Sandeep Yadav (Research Scholar, Chemistry). Right: A peacock perches on the roof of the RA Hostel, against a backdrop of gulmohar flowers. Picture Credit: Prof Praveen Kulshreshtra (Dept of Economics).

148

---

Bottom Left: Sixth Avenue, the main connector road between the residence halls. Clicked from Hall IV, looking towards the Pool. Visible also, is the road bridge over the small canal that used to flow through the campus. Picture Credit: Shashank Chaudhary (M Design 2018-20). Right: The Open Air Theatre (OAT) at the new SAC. Picture Credit: Tanya Srivastava (R&D Office)

149

---

150

---

"Seeing this, I feel like spending another year in the institute. Without classes, assignments, quizzes, midsems and endsems..."-Vinay Shripad Panchanadikar (BT, ME, 1978-83)
The pictures for this story were contributed by members of the FaceBook group 'This Bit of That IITK'.

Cover Pictures:

Front Top: A View of the Academic Area from the roof of L-20. Clicked by Aditya Raghav Trivedi (BT, BSBE, 2018-22). Bottom: Sixth Avenue, looking from Hall IV (visible on the right) towards the Airstrip. Clicked by Himadri Roy (Research Scholar, Physics)
Back: "An Overflow of Knowledge at the Library". A long exposure shot of "The Crow" by Granth Choudhary (BT, EE, 2020-24)

151

---