BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//TIFR STCS//Student Seminar Series//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:TIFR STCS Student Seminars
X-WR-TIMEZONE:Asia/Kolkata
X-WR-CALDESC:Weekly student seminars at TIFR STCS. Subscribe to receive future talks automatically.
BEGIN:VEVENT
UID:talk-2026-02-27@tcs.tifr.res.in
DTSTAMP:20260609T120945Z
DTSTART:20260227T103000Z
DTEND:20260227T113000Z
SUMMARY:Training a 3-node neural network is NP-complete — Nishant P. Das (STCS)
DESCRIPTION:In this work\, the authors consider a 2-layer\, 3-node\, n-input neural network whose nodes compute linear threshold functions of their inputs. They show that it is NP-complete to decide whether there exist weights and thresholds for this network so that it produces output consistent with a given set of training examples. They also extend the result to other simple networks. Furthermore\, they also present a network for which training is hard but where switching to a more powerful representation makes training easier. These results suggest the importance\, given a training problem\, of finding an appropriate network and input encoding for that problem.
LOCATION:A-201\, TIFR Mumbai
URL:https://www.tcs.tifr.res.in/~student_seminar/talks/2026-02-27/
END:VEVENT
BEGIN:VEVENT
UID:talk-2026-04-24@tcs.tifr.res.in
DTSTAMP:20260609T120945Z
DTSTART:20260424T103000Z
DTEND:20260424T113000Z
SUMMARY:Teaching your computer to play chess (Part 1): Markov Games and TD Learning — Aakash Ghosh (STCS)
DESCRIPTION:How do we mathematically formulate the problem of learning to play a game as complex as chess? In the first part of this two-part series\, we will approach chess through the lens of Reinforcement Learning and Stochastic Approximation. We begin by formalizing the game as a two-player zero-sum Markov Decision Process\, discussing the Bellman Optimality Equation and minimax equilibria.
LOCATION:A-201\, TIFR Mumbai
URL:https://www.tcs.tifr.res.in/~student_seminar/talks/2026-04-24/
END:VEVENT
BEGIN:VEVENT
UID:talk-2026-05-08@tcs.tifr.res.in
DTSTAMP:20260609T120945Z
DTSTART:20260508T103000Z
DTEND:20260508T113000Z
SUMMARY:Teaching your computer to play chess (Part 2): Bandits\, MCTS\, and Approximate Policy Iteration — Aakash Ghosh (STCS)
DESCRIPTION:Building on the theoretical limitations of pure TD-learning explored in Part 1\, how do modern neural engines like AlphaZero actually master the game? In the second part of this series\, we shift our focus to local search framed as a sequential decision-making problem under uncertainty. We will introduce the Multi-Armed Bandit problem and the UCB1 algorithm\, extending these concepts to game trees via Monte Carlo Tree Search (MCTS). Finally\, we will deconstruct the AlphaZero framework\, demonstrating how it utilizes MCTS as a formal policy improvement operator to perform Approximate Policy Iteration and successfully evade the “Deadly Triad” of deep reinforcement learning.
LOCATION:A-201\, TIFR Mumbai
URL:https://www.tcs.tifr.res.in/~student_seminar/talks/2026-05-08/
END:VEVENT
BEGIN:VEVENT
UID:talk-2026-05-15@tcs.tifr.res.in
DTSTAMP:20260609T120945Z
DTSTART:20260515T103000Z
DTEND:20260515T113000Z
SUMMARY:Deterministic list decoding of Reed-Solomon codes — Soham Chatterjee (STCS)
DESCRIPTION:We show that Reed-Solomon codes of dimension $k$ and block length $n$ over any finite field $\\mathbb{F}$ can be deterministically list decoded from agreement $\\sqrt{(k-1)n}$ in time $\\text{poly}(n\, \\log |\\mathbb{F}|)$.\nPrior to this work\, the list decoding algorithms for Reed-Solomon codes\, from the celebrated results of Sudan and Guruswami-Sudan\, were either randomized with time complexity $\\text{poly}(n\, \\log |\\mathbb{F}|)$ or were deterministic with time complexity depending polynomially on the characteristic of the underlying field. In particular\, over a prime field $\\mathbb{F}$\, no deterministic algorithms running in time $\\text{poly}(n\, \\log |\\mathbb{F}|)$ were known for this problem.\nOur main technical ingredient is a deterministic algorithm for solving the bivariate polynomial factorization instances that appear in the algorithm of Sudan and Guruswami-Sudan with only a $\\text{poly}(\\log |\\mathbb{F}|)$ dependence on the field size in its time complexity for every finite field $\\mathbb{F}$. While the question of obtaining efficient deterministic algorithms for polynomial factorization over finite fields is a fundamental open problem even for univariate polynomials of degree $2$\, we show that additional information from the received word can be used to obtain such an algorithm for instances that appear in the course of list decoding Reed-Solomon codes.
LOCATION:A-201\, TIFR Mumbai
URL:https://www.tcs.tifr.res.in/~student_seminar/talks/2026-05-15/
END:VEVENT
BEGIN:VEVENT
UID:talk-2026-05-22@tcs.tifr.res.in
DTSTAMP:20260609T120945Z
DTSTART:20260522T103000Z
DTEND:20260522T113000Z
SUMMARY:Towards Provable Leakage-Resilience of Additive and Inner-Product Masking under Hamming-weight Model — Jihun Hwang (Jimmy) (Purdue University)
DESCRIPTION:Additive secret sharing achieves perfect secrecy: even if a strict subset of shares is leaked\, the secret remains completely hidden. But is this still the case when partial information on every share leaks?\nWe study the local leakage resilience of additive secret sharing (and its variants) against Hamming-weight leakage in two settings.\nOver binary extension fields (Boolean hypercubes)\, we show that inner-product secret sharing (where the secret is reconstructed as an inner product of the shares with a fixed vector) is secure against Hamming-weight leakage unless the reconstruction vector is constant. We also introduce an efficiently computable score function that quantifies and certifies the security afforded by a given reconstruction vector. Over near-dyadic-order groups\, we show that additive secret sharing is secure against Hamming-weight leakage. We prove matching upper and lower bounds on insecurity\, establishing that our bounds are tight. As a byproduct\, we obtain a ternary representation result: the Cayley graphs of near-central Hamming slices have diameter at most three. Our analysis is Fourier-analytic\, combining techniques from Krawtchouk polynomials\, additive combinatorics\, and spectral methods.
LOCATION:via Zoom in A-201\, TIFR Mumbai
URL:https://www.tcs.tifr.res.in/~student_seminar/talks/2026-05-22/
END:VEVENT
BEGIN:VEVENT
UID:talk-2026-05-28@tcs.tifr.res.in
DTSTAMP:20260609T120945Z
DTSTART:20260528T103000Z
DTEND:20260528T113000Z
SUMMARY:Polynomial Time Local Decision Revisited — Soumyadeep Paul (STCS)
DESCRIPTION:We consider hierarchies related to distributed decision problems: unbounded computation time and unbounded certificates\, as defined by Balliu\, D’Angelo\, Fraigniaud\, and Olivetti [JCSS’18]\, and two other hierarchies that polynomially bound computation and certificate size\, defined by Aldema Tshuva and Oshman [OPODIS’23]\, and by Reiter [PODC’24]. The two definitions for polynomially bounded local computation differ in the parameter they are polynomial in: Aldema Tshuva and Oshman consider being polynomial in the size of the graph while Reiter considers each node being polynomial in the size of its local neighborhood.\nI will define the LOCAL model of distributed computation\, distributed decision tasks in this model and relationships between classes of the three hierarchies.
LOCATION:A-201\, TIFR Mumbai
URL:https://www.tcs.tifr.res.in/~student_seminar/talks/2026-05-28/
END:VEVENT
BEGIN:VEVENT
UID:talk-2026-06-05@tcs.tifr.res.in
DTSTAMP:20260609T120945Z
DTSTART:20260605T103000Z
DTEND:20260605T113000Z
SUMMARY:Binary Hypothesis Testing with Deterministic Finite Memory — Malhar A. Managoli (STCS)
DESCRIPTION:Binary hypothesis testing is a classic problem in statistics. Classically\, the goal of the problem is to minimize the probability of error as a function of the number of samples. In the finite memory version of the problem\, samples are plentiful\, but we have only a small amount of memory to work with. This is modeled as the tester being a finite automaton. In a previous talk\, we have seen the result for the case when the automaton is randomised. In this talk\, we will consider the deterministic case. Although tight results are not known in this case\, we can show that deterministic automatons are weaker than their randomised counterparts.
LOCATION:A-201\, TIFR Mumbai
URL:https://www.tcs.tifr.res.in/~student_seminar/talks/2026-06-05/
END:VEVENT
BEGIN:VEVENT
UID:talk-2026-06-10@tcs.tifr.res.in
DTSTAMP:20260609T120945Z
DTSTART:20260610T103000Z
DTEND:20260610T113000Z
SUMMARY:Deterministic Algorithms for Low Individual Degree Factors of Sparse Polynomials — Rishabh Kothary (University of Toronto)
DESCRIPTION:Polynomial factorization is a central problem in computational algebra and algebraic complexity\, with connections to many areas in theoretical computer science. Even for the case of sparse multivariate polynomials there is a lot we do not understand- we only know subexponential time deterministic factoring algorithms for sparse polynomials by the recent work of Bhattacharjee\, Kumar\, Rai\, Ramprasad and Saraf. In the case where the input sparse polynomial has constant individual degree\, we know how to factor deterministically in quasipolynomial time by the work of Bharagava\, Saraf and Volkovich and a recent improvement by Chuyoon and Shpilka.\nIn this work we give a deterministic polynomial time algorithm that takes as input a sparse polynomial of constant individual degree and outputs a list of circuits such that every factor of the input is in the list. One caveat is that the list might contain additional spurious circuits that are not factors. We also give a quasipolynomial time deterministic algorithm that takes as input a general sparse polynomial and outputs a list of circuits such that every factor of the input of constant individual degree is in the list. Again the list might contain additional spurious circuits. A consequence of our algorithm is a new upper bound on the total number of bounded individual degree factors of a sparse polynomial.\nThis is based on joint work with Somnath Bhattacharjee (U of T)\, Shanthanu S. Rai (TIFR) and Shubhangi Saraf (U of T).
LOCATION:A-201\, TIFR Mumbai
URL:https://www.tcs.tifr.res.in/~student_seminar/talks/2026-06-10/
END:VEVENT
BEGIN:VEVENT
UID:talk-2026-06-19@tcs.tifr.res.in
DTSTAMP:20260609T120945Z
DTSTART:20260619T103000Z
DTEND:20260619T113000Z
SUMMARY:TBD — Sayan Kar (ISI Kolkata)
DESCRIPTION:TBD
LOCATION:A-201\, TIFR Mumbai
URL:https://www.tcs.tifr.res.in/~student_seminar/talks/2026-06-19/
END:VEVENT
BEGIN:VEVENT
UID:talk-2026-06-26@tcs.tifr.res.in
DTSTAMP:20260609T120945Z
DTSTART:20260626T103000Z
DTEND:20260626T113000Z
SUMMARY:Introspectively Envy-Free and Efficient Allocation of Indivisible Mixed Manna — Paritosh Verma (University of Toronto)
DESCRIPTION:TBD
LOCATION:Via zoom at A-201\, TIFR Mumbai
URL:https://www.tcs.tifr.res.in/~student_seminar/talks/2026-06-26/
END:VEVENT
END:VCALENDAR