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

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

TBD

TBD