About the research area
I am keen to have interns who are intersted in exploring topics in Complexity Theory and Analysis of Algorithms. Our focus is on Algebraic Complexity Theory, Analysis of Boolean Functions and Analysis of Algorithms.
Typical problems we think about involve structural and algorithmic questions such as:
- Algebraic Complexity Theory: arithmetic circuits, polynomial identity testing, lower bounds.
- Analysis of Algorithms: average‑case and smoothed analysis .
- Graph Coloring Problems: structural properties, hardness, and algorithmic approaches.
- Boolean Functions: Fourier analysis, learning‑theoretic questions, and complexity measures.
- Data Structures: Design and analysis of fundamental data structures.
- Complexity Theory
- Combinatorics
- Boolean Function Analysis
- Graph Algorithms
- Data Structures
Why intern with us?
Exposure to frontier problems
As an intern, you will engage with problems that are at the frontier of current research. You will see how ideas from algebra, combinatorics, and probability come together to answer fundamental questions in theoretical computer science.
Problem‑driven learning
The main task will invlove reading research papers, reconstructing proofs, exploring variants, and trying to push known results further. The goal is to help you develop the ability to ask questions and reason rigorously.
Preparation for research careers
This internship is particularly suitable if you are considering a future MS/PhD in theoretical computer science or related areas. You will get a realistic sense of what research feels like, and whether you enjoy the style of work involved in complexity theory and algorithms.
What you might work on
- Small projects on arithmetic circuits – exploring restricted models or special classes of polynomials.
- Complexity parameters of Boolean functions – sensitivity, degree, Fourier spectrum, and learning aspects.
- Graph coloring and structural questions – reductions, hardness, and algorithmic heuristics.
- Data structure lower bounds – understanding fundamental questions in data structures and algorithms.
- Survey‑style projects – synthesizing a line of work into a coherent, accessible write‑up.
Who will be a good fit?
These internships are best suited for students who already enjoy thinking abstractly and are comfortable with mathematical reasoning. You need not know everything about complexity theory. A curious mind with mathematical maturity and willingness to put efforts understanding in rigourous mathematical arguements are essential.
- Background: senior undergraduate or early graduate students in Computer Science, Mathematics, or related areas.
- Core skills: strong foundations in discrete mathematics, algorithms, theory of computation, and basic probability.
- Desirable exposure: courses in complexity theory, algebra, graph theory, or Boolean function analysis.
- Working style: patient with proofs, comfortable reading and discussing research papers.
Expectations
The internship is designed as a serious academic engagement. To make it meaningful for both you and the group, we look for the following:
- Commitment: ability to devote sustained time over the internship period, rather than sporadic effort.
- Curiosity: willingness to ask questions, challenge assumptions, and explore alternative approaches.
- Communication: readiness to present your understanding in writing and in informal talks or discussions.
- Independence: comfort with working through technical details on your own before seeking guidance.
How to express interest
Internship positions may be limited and are typically aligned with ongoing research directions. If you feel that your interests strongly match the themes above, you can:
- Prepare a brief statement of interest: 1–2 pages describing:
- What makes you curious about theoretical computer science?
- Courses you have taken relevant to algorithms, complexity, and mathematics.
- Any prior exposure to research (projects, reading groups, independent study).
- Specific topics from the list above that you find most exciting and why.
- Attach a concise CV: highlighting academic performance, relevant theory/math projects.
- Mention prior exposure: if you have read particular papers or books in complexity theory or algorithms, list them.
For formal internship programmes at IIT Madras, please refer to the institute’s official internship portals. For information about MS/PhD positions and broader research opportunities, see my main page. – IIT Madras.