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.

TBD

TBD