Akanksha Agrawal

Eminent Speaker

Short CV:

Akanksha primarily works in the area of parameterized algorithms, and her interest spans algorithmic problems on graphs and in computational geometry. She is currently an Assistant Professor at Dept. of Computer Science & Engg., Indian Institute of Technology Madras. Akanksha has served as a program committee member for several reputed international conferences, and she is currently editorial board member for two journals. She has been an invited speaker at various international and national venues, including an invited speaker for a conference. She has been co-organizer for seminars and schools in the field of Algorithm Design, including an ACM-India Winter School. Akanksha has over 50 publications and two invited surveys.

Title of Talk 1: Beyond the Input Size: A Gentle Introduction to Parameterized Algorithms

Synopsis: There are ample examples from the early years of Computer Science that suggest input size is not the only governing factor in the runtime complexity of a problem. A few such examples that one can pick from some basic Algorithms textbooks are: 1) Radix Sort, where the running time changes based how many bits we use to represent the input numbers, 2) classicalgraph problems on tree(-like) graphs, and 3) Minimising maximum lateness in a schedule while taking into account the number of distinct arrival times. This indicates that certain structurallyuseful features of the input/output may dramatically simplify the job for us. Parameterized Algorithms is precisely the study of how a secondary measure, called as the parameter, affects the complexity of the problem. The aim of the talk is to introduce the area of Parameterized Algorithms & Complexity, and learn some very basic techniques used in obtaining suchalgorithms.

Title of Talk 2: Research in Algorithms-What is it this fuss about?

Synopsis: We will take a brief walk through the timeline of algorithms in your life, starting way l the way up to your grad school where you saw more complicated algorithms, and perhaps classes like P and NP. We will see how mathematics helps us in obtaining correct and faster algorithms, and how ubiquitous algorithms and mathematics are. We will revisit some fundamental problems and brush through the developments we have achieved for theseproblems in the recent years, and see how much we still do not understand about the algorithmic complexity of some of the very fundamental problems.

Title of Talk 3: Algorithms: To improve, or not to improve, that's the question

Synopsis: There are only a handful of problems, like Sorting, for which we have achieved algorithms with the best possible running times (at least comparison-based). For most other fundamental problems like Graph Diameter, All-pairs Shortest Paths, Boolean Matrix Multiplication, and 3-SUM, we have neither seen "significantly improved" algorithms, nor results like that for sorting, which guarantee that the existing algorithms are the best possible ones. In the recent years, we have seen an interesting progress in our understanding of some very fundamental problems: i) for some, we have managed to obtain lower order algorithmic improvements, and ii) for many problems we have managed to obtain connections between algorithmic improvements (an improved algorithm for one immediately gives improved algorithms for several others). We will look at some of these algorithmic connections and the hardness theory for polynomial time solvable problems. We will also see a simple look-up based approach in obtaining a faster algorithm for a classical problem.

Akanksha Agrawal

Qualifications: PhD

Title: Assistant Professor

Affiliation: Indian Institute of Technology Madras, Chennai

LinkedIn:

Twitter/X:

Facebook:

Instagram:

Email: [email protected]

About the speaker: