Special Interest Group on Theoretical Aspects of Computer Science was born out of an effort to bring together people interested in areas of Theoretical Computer Science. It is a platform for students and faculty members to come together and share their excitement in the area. The group aims at organizing problem solving sessions, seminars and guest lectures.
KD102, 11:00 am, Tuesday 9th December 2025
A central question in algebraic complexity is how polynomial computation models behave under basic algebraic operations. While most standard models are closed under addition and multiplication, closure under factorisation is much more subtle. This talk presents a new result showing that read-once oblivious algebraic branching programs (roABPs) are not closed under factorisation, and discusses related non-closure results under operations such as powering and symmetric composition.
This talk is based on joint work with Andrews, Armand, Hansen, Limaye, Srinivasan, and Tavenas. [arXiv]
KD 102, 5:30 pm, Monday 27th October 2025
Computational complexity of a problem is a measure of computational resources—time, memory, circuit size/depth—needed to compute the output for any given instance of the problem. In the dynamic setting, the input instance evolves over time, and one is expected to update the output after each change. The goal is to avoid re-computation from scratch after every change, and instead apply an update program to stored auxiliary data to obtain the new output. The dynamic complexity of a problem measures the resources required by such an update program.
In 1994, Patnaik and Immerman introduced an elegant framework from descriptive complexity, defining the class DynFO. In the version considered here, the first-order update formulas have access to built-in arithmetic (equivalently, AC0 circuits or constant-time algorithms on CRCW PRAM). In recent years, DynFO has seen remarkable progress: reachability, CFL membership, tree isomorphism, MSO queries on bounded-treewidth graphs, abelian group isomorphism, and planarity testing are now known to be maintainable within DynFO.
This talk will introduce the ideas behind DynFO, survey key developments, and highlight open directions. Time permitting, it will also discuss a recent result on dynamic tree isomorphism based on joint work with Samir Datta.
KD102, 5:30 pm, Tuesday 23rd September 2025
Boolean functions are fundamental in CS, with measures like query complexity, block sensitivity, certificate complexity and degree capturing their difficulty. While these measures are polynomially related, the tightness of those relations remains open. For certain subclasses we can improve bounds — one such class is Zebra functions (Chugh, Poddar & Sanyal, 2023). This talk introduces Zebra functions, explains their relevance, and outlines improved upper bounds for them.
KD102, 5:30 pm, Thursday 28th August, 2025
It seems intuitive that giving a computer an extra hard drive full of critical data does not aid computation. However, Cook and Mertz have discovered that such a memory -- if used in a "catalytic" way -- can actually help. Their surprising idea shows that additional memory can be valuable even when its contents must be fully restored after the computation is complete. This result was used for space-efficient Turing machine simulation, as observed in the last talk.
The talk is based on the work of Cook and Mertz. See [1], [2], and [3].
KD102, 5:30 pm, Thursday 21st August, 2025
In this talk we will discuss the proof of a breakthrough result by Ryan Williams, showing that all algorithms can be simulated using considerably less memory than the time of the original algorithm.
The talk is based on the work of Ryan Williams. See [1] and [2].
KD103, 3:30 pm, Thursday 14th August, 2025
For sequential prediction tasks, Solomonoff’s (1978) celebrated result guarantees the inductive success of the “simplicity” prior by showing that the predictive probabilities induced by any optimal c.e. semimeasure converge to the posterior of the true probability almost surely. Hutter and Muchnik (2006) have shown that there exists an optimal c.e. semimeasure for which one can construct a Martin-Löf sequence along which this optimal semimeasure fails to converge to the uniform measure. Since the study of algorithmic randomness can be used to characterize “almost-sure” convergence theorems, one can ask whether stronger notions of randomness suffice for Solomonoff convergence.
We show that the minimal strength of randomness required for off-sequence convergence is at most 2-computable randomness; this establishes an upper bound on the weakest notion of randomness that ensures the success of Solomonoff induction. Furthermore, due to its rejection of Turing incomplete sequences as random, difference randomness prima facie appears to be the weakest notion that could guarantee convergence. Contrary to this intuition, we prove a negative result with respect to the uniform measure. The machinery of this proof can be extended to show that any notion of randomness that does not guarantee convergence of all c.e. supermartingales will always yield a negative result for Solomonoff convergence.
Bio: Damini is a PhD student in the Department of Philosophy at Carnegie Mellon University. Her primary research interest is in algorithmic randomness. She is also interested in logic, particularly as it pertains to areas in formal epistemology, as well as in the philosophy and history of mathematics.
KD103, Part 1 - 4:30 pm, Wednesday 28th May; Part 2 - 11:00 am, Thursday 29th May, 2025
This talk aims to understand the efficient algorithm for factoring polynomials over finite algebraic extensions of the p-adic numbers. The known p-adic factoring algorithms are due to A.L. Chistov (1987) and by Cantor & Gordon (2000).
This talk is based on the work of David G. Cantor and Daniel M. Gordon from 2000 – Factoring polynomials over p-adic fields. This work uses the ideas of Chistov’s randomized polynomial-time algorithm and is suitable for practical implementation.
Plan for this talk:
Day 1: On the first day, we will try to learn about the p-adic numbers and a little
bit of p-adic analysis. Then we will see Modified Hensel Lifting.
Day 2: On the second day, we will see the main p-adic algorithm.
Those who are interested in Algebra, Algebraic Number Theory, and Computational Algebra may find this talk interesting.
KD103, 4:00 pm, Tuesday 4th February 2025
Multivariate cryptography has garnered significant attention, particularly following the recent NIST standardization of additional signature schemes. Notably, the second round of the competition featured five schemes: SNOVA, MAYO, UOV, QR-UOV, and MQOM. Apart from MQOM, all of these follow the well-studied Unbalanced Oil and Vinegar (UOV) principle.
This talk will delve into the foundational design principles of the UOV scheme and its influence on the development of other signature schemes. We will also explore the challenges associated with the implementation security of UOV and discuss strategies to address them. Finally, we will examine the potential for extending UOV signature schemes into a blind signature context, highlighting its implications for privacy and secure communication.
KD102, 4:00 pm, Thursday 7th November 2024
A sunflower is a collection of sets whose pairwise intersections are identical. In this article, we shall go sunflower-picking. We find sunflowers in several seemingly unrelated fields, before turning to discuss recent progress on the famous sunflower conjecture of Erdős and Rado, made by Alweiss, Lovett, Wu and Zhang, as well as a related resolution of the threshold vs expectation threshold conjecture of Kahn and Kalai discovered by Park and Pham. We give short proofs for both of these results.
The talk is based on this paper.
KD101, 4:00 pm, Wednesday 21st August 2024
Hausdorff dimension generalizes the idea of dimensionality to non-integer values, while its effective analogue, constructive dimension, captures the information rate of infinite binary strings. A key link between these notions is the Point-to-Set Principle, relating sequence complexity to the fractal dimension of sets.
In this talk, we introduce Hausdorff Φ-dimension and its effective version, constructive Φ-dimension, and prove a generalized Point-to-Set principle. We then study the concept of faithfulness—when restricted covers preserve dimension—and show that for Cantor coverings, faithfulness at the Hausdorff and constructive levels coincide.