TIFR STCS Student Seminar Series

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.

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.

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.

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}|)$.

Prior 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.

Our 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.

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?

We study the local leakage resilience of additive secret sharing (and its variants) against Hamming-weight leakage in two settings.

1. Over 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.
2. 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.

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.

I will define the LOCAL model of distributed computation, distributed decision tasks in this model and relationships between classes of the three hierarchies.

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.

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, Ramanathan, Saptharishi 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.

In 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.

This is based on joint work with Somnath Bhattacharjee (U of T), Shanthanu S. Rai (TIFR) and Shubhangi Saraf (U of T).

Private Information Retrieval (PIR) schemes are communication protocols that allow a user to recover a single bit from a large database stored across multiple non-interacting servers, without revealing any information about which bit was queried. PIR schemes have deep connections to algebraic coding theory, and in particular to Locally Decodable Codes (LDCs).

In this talk, new $t$-server PIR schemes are presented with communication complexity subpolynomial in the previously best known bounds, for all but finitely many $t$. The key ingredients are matching vectors and polynomial derivatives, both well-established tools in the PIR and LDC literature. A landmark result of Dvir and Gopi previously combined these two ideas using polynomials and derivatives over exotic algebraic rings, giving the first $2$-server PIR with subpolynomial communication. The new approach achieves improved bounds via a simpler method that works natively over finite fields, using only elementary properties of polynomials. In particular, this obtains a $3$-server PIR with communication $2^{\tilde{O}((\log n)^{1/3})}$, improving upon the bound of $2^{\tilde{O}(\sqrt{\log n})}$ due to Efremenko.

The existence of allocations that are simultaneously fair and efficient is a central inquiry in the fair division literature. A prominent result in discrete fair division shows that the complementary desiderata of fairness and efficiency can be achieved together when allocating indivisible items with nonnegative values; specifically, allocations that are both envy-free up to one item (EF1) and Pareto efficient (PO) always exist for indivisible goods and additive valuations. While a recent breakthrough extends the EF1 and PO guarantee to indivisible chores (items with negative values), the question remains open for indivisible mixed manna, where values can be positive, negative, or zero.

The talk will describe our recent work that makes notable progress in resolving this central question. For indivisible mixed manna and additive valuations, we establish the existence of allocations that are PO and introspectively envy-free up to one item (IEF1). In an IEF1 allocation, each agent can eliminate its envy towards all the other agents by either adding an item or removing an item from its own bundle. The notion of IEF1 coincides with EF1 for indivisible chores, and hence, our result generalizes the aforementioned existence guarantee for chores. Our techniques can be adopted to obtain an alternative proof for (in fact a generalization of) the existence of EF1 and PO allocations of indivisible goods, as well as recover a distinct proof for the existence of PO and envy-free allocations of divisible mixed manna.

Hence, our results provide a unified approach that subsumes several state-of-the-art existence results concerning fair and efficient allocation of both indivisible and divisible items.

Based on joint work with Dr. Siddharth Barman (IISc)

For a time, it was common to dismiss large language models (LLMs) as “just autocomplete” and therefore fundamentally incapable of sophisticated reasoning. Yet modern LLMs exhibit capabilities that would have seemed impossible only a few years ago, the latest of which is disproving a longstanding conjecture of Erdős on the unit distance problem. One might attribute this progress to larger models and larger training corpora, but this is far from the whole story: after one has already scraped most of the available high-quality text on the internet, obtaining substantially more training data becomes challenging. Instead, much of the recent progress has come from innovations in how LLMs are trained. In this talk, we will trace the evolution of post-training and inference procedures (RLHF, DPO, RLVR, test-time compute, etc.) that have transformed LLMs into much more than mere autocomplete.

In this talk, we will go over lower bounds for roABP-IPS refutations of Boolean CNF formulas. Earlier IPS lower bounds were mostly known for algebraic systems of equations, rather than CNF formulas, which are the standard objects in propositional proof complexity. We will discuss how the paper obtains such lower bounds using a feasible interpolation argument, where short roABP-IPS refutations would imply small monotone span programs for the corresponding interpolants. Therefore, lower bounds for monotone span programs can be used to give lower bounds for roABP-IPS refutations.

In an era of big data, the ability to distinguish between mere correlation and true causation is arguably the most critical skill for researchers and data scientists. This talk attempts to provide a conceptual introduction to the modern framework of causal inference. We will explore how to move from “seeing” to “doing” by using Directed Acyclic Graphs (DAGs) to model the causal structure of the world. We will learn how to identify causal effects, apply the Backdoor Criterion to mitigate the biases of confounding, and also address the challenge of “transportability”—taking findings from one context and applying them to another.

We study the problem of robustly learning Gaussian Single Index Models (SIMs) in the presence of heavy-tailed noise and a constant fraction of adversarially corrupted covariates and responses. Prior work on robust recovery has considered settings such as linear regression (Pensia et al., JASA 2024), strictly monotonic link functions (Awasthi et al., NeurIPS 2022), and phase retrieval (Buna and Rebeschini, AISTATS 2025). However, these techniques do not extend to generic asymmetric non-monotonic link functions such as GeLU and Swish, which arise naturally as scalar primitives in modern gated neural architectures. We close this gap by giving the first robust recovery algorithm with near-linear sample and time complexity for generic non-monotonic link functions, thereby establishing the first robust recovery guarantees for a broad family of nonlinear SIMs for which no guarantees were previously known. Our central contribution is a new structural understanding of the Gaussian squared-loss landscape under adversarial contamination. Crucially, we prove that for a broad class of nonlinear non-monotonic SIMs, a dimension-independent, constant-radius convex basin exists around the ground truth and is efficiently reachable via robust spectral initialization even under adversarial contamination. Prior works fail to establish both guarantees simultaneously, thereby either breaking down under adversarial contamination or failing to handle generic non-monotonic link functions. Together, these structural insights yield a principled warm start for robust gradient descent that provably converges to a final estimation error of $O(\sigma \epsilon^{1/2})$ in $\widetilde{O}(nd)$ time with $\widetilde{O}(d)$ samples, where $\epsilon$ is the contamination fraction.

The central goal of secure multiparty computation (MPC) is to design a communication protocol for $n$ parties $P_1, P_2, \dots, P_n$, where $P_i$ holds private input $x_i$, to jointly compute a distributed functionality $f(x_1, \dots, x_n)$. Further, we require that each party learns nothing about the private inputs of the other parties (beyond what is revealed by the output of the functionality).

We will see the working of the IPS protocol compiler, which allows us to build MPC protocols that remain secure when a dishonest majority of the parties are corrupted, from component protocols that satisfy weaker security guarantees. The IPS paradigm is of particular interest in the design of black-box MPC protocols from minimal cryptographic assumptions.

This talk is based on the paper “Founding Cryptography on Oblivious Transfer – Efficiently” by Yuval Ishai, Manoj Prabhakaran and Amit Sahai.

Consider a gambler who repeatedly bets a fraction of her wealth on the outcome of an adversarially chosen coin, and suppose we ask only that her wealth grow at a certain rate relative to that of the best fixed betting fraction in hindsight. This talk develops the observation, due to Orabona and Pál, that this elementary game is not merely an analogy for online learning but is equivalent to it: a betting algorithm with a suitable wealth guarantee mechanically yields parameter-free algorithms for online linear optimization over Hilbert spaces and for learning with expert advice, with regret bounds that adapt to the unknown comparator without oracle tuning of a learning rate.

Imagine a device that multiplies two matrices very fast, but unreliably: only a small constant fraction of the entries in its output are correct, and even this is guaranteed only when the input matrices are random. On the matrices you actually care about, it may behave arbitrarily badly. Can such a device still be useful?

In this talk, we will see a recent result of Hirahara and Shimizu (STOC 2025) showing that the answer is yes, in the strongest possible sense: any such device can be converted into a fast randomized algorithm that computes matrix multiplication exactly, on all inputs. Over a finite field with $p$ elements, one can always get a $1/p$ fraction of entries right by blind guessing; the result shows that any algorithm doing even slightly better than this trivial baseline can be fully error-corrected, so the threshold is optimal. This is what is called a “worst-case exact to average-case approximate” reduction, and it resolves a question left open by earlier work on the average-case complexity of matrix multiplication.

A central idea in the proof comes from the theory of error-correcting codes. Instead of feeding the matrices $A$ and $B$ to the unreliable device directly, we first encode them: applying a linear code with encoding matrix $Q$, we hand the device the matrices $QA$ and $(QB^{\perp})^{\perp}$. The point is that the product of these encoded matrices equals $QABQ^{\perp}$, which is precisely the answer $AB$ encoded from the left and the right. The device’s noisy output is therefore a corrupted codeword of this two-sided encoding, and if the underlying code is a good list-decodable, such as the Reed-Solomon code, we can decode it column by column and then row by row to recover a short list of candidates containing $AB$, from which the true product is identified by a fast randomized verification. The talk will be self-contained and should be accessible to anyone comfortable with basic linear algebra and probability.

In offline-online multi-party computation protocols, the offline phase often involves setting up of input-independent random variables and the online phase involves a fast computation of the function once the inputs arrive. Unfortunately, the offline phase can be slow and can involve a lot of communication between parties. Pseudo-random correlation generators (PCGs) partially solve this problem by letting the parties communicate small correlated seeds and then letting them expand them locally to generate long correlated strings for the online phase. In this talk, we will see the construction of a PCG by Boyle, Couteau, Gilboa, Ishai, Kohl and Scholl, CRYPTO-2019.

Since this talk falls on 9/11, we will be careful about confident predictions: sometimes the right action is to abstain. We study online prediction with N experts and binary outcomes. Without abstention, the standard regret rate is Θ(√(T log N)). Neu and Zhivotovskiy show that allowing the learner to abstain at cost c < 1/2 changes the rate to Θ(min{log N / (1 − 2c), √(T log N)}). Thus, for fixed c < 1/2, regret eventually stops growing with the number of rounds. We will derive the algorithm from exponential weights, explain why its abstention probability tracks expert disagreement, and prove the upper bound through a one-variable inequality. We will then discuss the matching lower bound, varying abstention costs, and extensions to multiclass and infinite expert classes.

Fair division studies how to allocate items among agents while satisfying fairness requirements. This work focuses on indivisible items with nonnegative marginal values. For binary submodular valuations, where each marginal value is either zero or one, the Yankee Swap algorithm computes an allocation that simultaneously satisfies envy-freeness up to any good (EFX), maximum utilitarian social welfare (Max-USW), and maximum Nash welfare (MNW) in polynomial time. We introduce Submodular Preferences Over Complements (SPOC), where each agent specifies a matching over the goods and has a binary submodular valuation over these complements. This captures applications such as course allocation, where a student may value two complementary courses only when taken together.

For SPOC valuations, we show that envy-freeness up to one good (EF1) and Pareto optimality (PO) need not coexist, ruling out a general guarantee of EFX and Max-USW. However, we give a polynomial-time algorithm that simultaneously achieves EFX, a (1/3)-approximation to Max-USW, and a (1/(3+1/n))-approximation to the maximin share (MMS), where n is the number of agents. The welfare guarantee is almost to tight: there are instances where no EF1 allocation achieves more than half the optimal utilitarian welfare. We also prove that maximizing utilitarian welfare is APX-hard and provide polynomial-time algorithms for a (1/2)-approximation to Max-USW and later another polytime algorithm that produces an allocation which is ((5,1))-MNW allocation.

TBD

TBD

Minimum cuts are fundamental objects in graph theory. They often admit interesting combinatorial results like the Maxflow-Mincut Theorem and compact representations like the Gomory-Hu tree. The classical Gomory-Hu tree shows that although there are overall $\Omega(n^2)$ pairs of vertices, a single spanning tree compactly preserves all of their mincut values. But does any such structure survive when we move beyond the optimum?

We study this question for $k^{th}$ minimum value cuts, in short, \emph{$k^{th}$-mincuts}, for all pairs of vertices. We show that the Gomory–Hu phenomenon interestingly extends beyond minimum cuts: the $k^{th}$-mincut values between all pairs of vertices can be preserved by storing only $k$ spanning trees. This yields a tight bound of $O(\min{kn,n^2})$ on the number of distinct values. Going beyond values, we show that the cuts themselves also admit a compact representation: a collection of only $O(k\log n)$ tree-like structures suffices to store a $k^{th}$ mincut for each pair of vertices. These structural results further lead to compact data structures that given any pair of vertices $(u,v)$, can report a $k^{th}$ $(u,v)$-mincut and its value efficiently.

Overall, in this talk, we show that the strong redundancies that exist among all-pairs mincuts does not disappear beyond the optimum – it continues to exists for all-pairs $k^{th}$ mincuts, even for $k>1$.