The Society for Promotion of Science of Science & Technology in India (SPSTI), with Chandigarh Chapter of the National Academy of Sciences India (NASI) and Chandigarh chapters of INSA & INYAS in association with Punjab Engineering College (PEC) (Deemed to be University), Chandigarh with support from Department of Science & Technology, Chandigarh Administration organised the eight lecture of seriesNobel, Abel, Turing and World Food Prizes. The lecture entitled “The 2021 Abel Prize awarded to László Lovász and Avi Wigderson” was delivered by Prof. Jaikumar Radhakrishnan on January 22, 2022, Saturday at 11.00 am. The session was attended online on zoom and many more viewed the same on the Facebook page of SPSTI.

The session was steered by Ms. Rajni Bhalla. Prof. Arun Kumar Grover, Former Vice Chancellor of Panjab University and Vice President of SPSTI gave brief introduction about the series. Dr. Sugandha Maheshwary from Department of Mathematical Sciences, Indian Institute of Science Education & Research (IISER), Mohali introduced the Guest of Honour, Prof. Kapil Hari Pranjape, Department of Mathematics, IISER Mohali, S. S. Bhatnagar Prize in Mathematical Sciences (2005). He said the connection between Mathematics and computing is eternal. However, due to the enormous influence of the Greek School of Mathematics on the development of Mathematics the conceptual or theoretical aspect of the subject often gets more emphasis. It is the Indo Arabic viewpoint and mathematics which originally emphasize the algorithmic and computational side over the logical side, which is not to say that they are in conflict, but that they complement each other. Due to the enormous growth or in our understanding of electrical machinery and semiconductors, this computational approach of tuning has seen a practical implementation using electrical circuits. The electrical circuits came later but unfortunately people mistakenly believe that computer science is only studied as an engineering discipline. In fact, Science of computing is a part of mathematics from ancient times.

The 2021 Abel Prize was awarded jointly to Laszlo Lovasz and Avi Wigderson for their foundational contributions to theoretical computer science and discrete mathematics, and their leading role in shaping them into central fields of modern mathematics. Prof. Jaikumar Radhakrishnan discussed Lovasz’s influential probabilistic local lemma and theta function, and Wigderson’s pioneering contributions to the area of hardness and randomness. The speaker Prof. Jaikumar Radhakrishnan was introduced by Dr. Neha Sardana, Assistant Professor, Metallurgical and Materials Engineering, Indian Institute of Technology Ropar. Prof. Jaikumar Radhakrishnan, School of Technology and Computer Science, Tata Institute of Fundamental Research, Mumbai awarded S. S. Bhatnagar Prize in Mathematical Sciences in 2008.

He began his lecture with the Lovasz’s Local Lemma. Starting with graph coloring problem he talked about local versus global problem. He said graph coloring is a fundamental problem in computer science and also discrete mathematics. He discussed the question if the graph doesn’t have any small cliques or even small cycles, does it mean that the graph can be easily colored? In 1954 Descartes write even if a graph has no cliques it might need many colors. In1959 Erdos showed there exists graphs where every neighborhood vertex looks like a tree, yet the graph is hard to color. Lovasz in 1968, while in high school, showed explicit construction of such graph where every local neighborhood looks like a tree but when graphs is considered as a whole large number of colors are needed. So, the local pictures sometimes do not capture global difficulties. Five year later Lovasz published paper explaining Lovasz’s Local Lemma. He further explained the zero-error communication. In Shannon’s 5/2 channel adjacent symbols may be confused, so with use of one channel only two messages can be sent, which mans only one bit of information can be sent. But, with two uses of the channel five messages can be sent, so is more channels are used can more messages be sent? To which Lovasz in 1978 gave the notion of theta function of a graph, which is upper bound on the number of messages for one use of the channel.  Also briefly talked about other relevant work by Lovasz like Lovasz Lenstra algorithm, chromatic number of the Kneser graph, volume estimation of convex bodies, ellipsoid method. Chromatic number of the Kneser graph. While talking about Lovasz work in chromatic number of the Kneser graph, he talks about field of topological combinatorics, with many deep and beautiful results, which included the work by K. S. Sarkaria, whi was at Department of Mathematics, Panjab University.

He further talked about theoretical Computer Science deals with problems and the computational problems involve inputs and outputs, where the input is a graph which are encoded and solution is a sort of an algorithm which starts with this input and allows to make the conclusion. One of the methods of understanding the complexity of the problem is using circuits that operates on the input bits and eventually produces the answer. The size of the circuit, the number of gates that are used in this circuit is said to be the complexity of the problem. To build circuits for larger input sizes, the number of gates that are needed in the circuit grows exponentially, which means it is not an efficient solution. Efficient solution means this number of gates in your solution in the circuit as a function of the input should grow gradually, that is in some polynomial. The dollar gates are used to model random actions of the algorithms, where errors are allowed but the algorithm must give correct answer with high probability. He said randomness is central to computation and the randomness computation noise is blessing unlike engineering as it helps to come up with efficient algorithms in situation where deterministic algorithm is not known. He talked about P and NP problems, where problems for which we have efficient solutions are called P problems and where when presented solution can be verified are called NP problems. He says if there are hard problems, which cannot be solved efficiently, the output of those problems can be used as randomness in algorithms. To explain this, he quotes theorem by Impagliazzo and Wigderson that “if there are problems that can be solved in exponential time, but not in (randomized) polynomial time, then all randomized algorithms can be derandomized” and this helps in pseudo numbers generator based on nearly disjoint subsets. He also talked about zero-knowledge proofs where theorem is validated without revealing the proof. He also shared the views of Lovász and Wigderson on science where they feel science has grown very fast and it becomes difficult to differentiate between science and pseudoscience, making science more frightening and difficult. They are of the view that we need to very carefully rethink how we teach students in high school and mathematics is one of the areas where teaching is not up to what it could be. He concluded his session stating “please teach, whatever you can, whenever you can, whomever you can”.

The session was very interactive and was much appreciated by the audience. Dr. Nishima Wangoo, Chandigarh Chapter of INYAS presented the vote of thanks. The information about future lectures in the series will be available on the SPSTI webpage and lectures can be accessed on the SPSTI Facebook page.