Siddharth Barman
Title: From Cake Cutting to Partitioning Graphs: A Tour Through Fair Division
The talk will start by recalling the result of Su (1999) that establishes the universal existence of envy-free cake divisions under mild assumptions. The proof of Su uses Sperner's Lemma, a result of topological combinatorics. We will show how envy-free cake division implies results in combinatorics, including the universal existence of balanced-cut-wise graph partitions.
I will also present approximation algorithms for efficiently finding envy-free cake divisions.
The talk will cover joint works with Eshwar Arunachaleswaran, Rachitesh Kumar, Nidhi Rathi, and Paritosh Verma.
Mrinal Kumar
Title: Algorithms for bivariate polynomial factorization
Bivariate polynomial factorization is the question of decomposing a given bivariate polynomial into the product of its irreducible factors. In this talk, we will see an overview of some of the main ideas in classical efficient algorithms known for this problem. One of the highlights will be an analog of the well known notion of Newton iteration to the setting of bivariate polynomials.
Title: Algorithms for noisy polynomial interpolation
Polynomial interpolation is the question of recovering the coefficient vector of polynomial from its evaluation on sufficiently many points. When some of these evaluations are erroneous, we end up with the question of noisy polynomial interpolation. A fundamental question of interest, both in coding theory and computational algebra, algorithms for noisy polynomial interpolation have been known in various settings since the 1960s. In this talk, we will discuss some of these algorithms in detail.
Naveen Garg
Title: Projection methods in online algorithms.
Abstract: Over the last decade online algorithms for many classical problems have been cast as mirror descent procedures. This viewpoint has led to development of projection-based algorithms for these problems which provide better competitive ratios. In this talk, I will present some of this work for setcover and weighted paging.
Pravesh Kothari
Title: Matrix Concentration and Applications to Algorithms and Combinatorics
Abstract: I will discuss matrix concentration inequalities and their applications to algorithm design and extremal combinatorics. Applications will include graph sparsification, solving certain beyond-worst-case instances of constraint satisfaction problems, and extremal girth problems in combinatorics.
Deeksha Adil
Title: Fast Algorithms for Regression Problems
Abstract: Increasing data sizes necessitates fast and efficient algorithms to analyze them. Regression is one such essential tool that is widely used. In this talk, I will focus on the "p-norm regression problem", which is a generalization of the standard "linear regression problem", and captures several important problems including the maximum flow problem on graphs. Historically, obtaining fast, high-accuracy algorithms for this problem has been challenging due to the lack of smoothness and strong convexity of the function, however, recent breakthroughs have been able to get around these issues. I will present an overview of how these algorithms work and discuss some generalizations of these techniques to other regression problems.
Jaikumar Radhakrishnan
Title : A short tutorial on mutual information
Abstract : In this tutorial we will discuss two asymptotic optimization problems in whose study Shannon's mutual information appears naturally. We will discuss the algorithm of Arimoto and Blahut to compute the optimum in these settings. We will largely follow the discussion in Csiszar and Korner's Information Theory book.
Anand Louis
Title: Recovering Planted Subgraphs
Abstract: Recovering a subgraph with a specified property hidden in a random graph is a fundamental problem in the study of algorithms. One of the central problems in this direction of study is the planted clique problem, where a clique is planted in an Erdos-Renyi random graph. The seminal work of Alon, Krivelevich and Sudakov (1998) gave an algorithm to compute planted cliques of size $\Omega(\sqrt{n})$; their algorithm was based on using the graph's spectra. This work has inspired numerous works on this and related problems using tools from random matrix theory, random graphs, "sum-of-squares" framework, convex optimization, and machine learning. In the first part, I will survey the history and some recent developments related to this problem. In the second part I will talk about some recent works on recovering planted bipartite graphs; this will be based on joint work with Rameesh Paul and Prasad Raghavendra.
Pravesh Kothari
Title: Matrix Concentration and Applications to Algorithms and Combinatorics
Abstract: I will discuss matrix concentration inequalities and their applications to algorithm design and extremal combinatorics. Applications will include graph sparsification, solving certain beyond-worst-case instances of constraint satisfaction problems, and extremal girth problems in combinatorics.
Ramya C
Title:On Relations in Polynomial Algebras
Abstract:
In this talk, we will walk through relations such as associativity and
commutativity in the polynomial ring and
define different polynomial algebras based on these axioms. We will
survey arithmetic circuit size lower bounds and algorithms for
polynomial identity testing and factorization in these algebras. Some
of the results outlined in this talk are based on discussions with
Partha Mukhopadhyay(CMI), Raja(IIT Tirupati) and Pratik Shastri(IMSc).
Jaikumar Radhakrishnan
Title : The communication complexity of correlation
Abstract : Consider a pair of random variables (X,Y) taking values in A x B with some joint distribution P. Suppose Alice is given a sample x distributed according to the marginal distribution of X. She needs to send a message to Bob so that he can generate a sample y whose distribution is exactly the distribution of Y conditioned on X=x. Let C[X:Y] denote the minimum number of bits Alice needs to send in expectation for this task (we allow Alice and Bob to share randomness). We will show that
I[X:Y] <= C[X:Y] <= I[X:Y] + O(log (I[X:Y] +1)) + O(1),
where I[X:Y] = H[X] + H[Y] - H[(X,Y)] is the Shannon mutual information of X and Y. This result provides an operational justification for the formula for mutual information. This talk will be based on a joint work with Prahladh Harsha, Rahul Jain, and David McAllester (IEEE Transactions on Information Theory, vol. 56, no. 1, pp. 438-449, Jan. 2010, doi: 10.1109/TIT.2009.2034824).
Anand Louis
Title: Recovering Planted Subgraphs
Abstract: Recovering a subgraph with a specified property hidden in a random graph is a fundamental problem in the study of algorithms. One of the central problems in this direction of study is the planted clique problem, where a clique is planted in an Erdos-Renyi random graph. The seminal work of Alon, Krivelevich and Sudakov (1998) gave an algorithm to compute planted cliques of size $\Omega(\sqrt{n})$; their algorithm was based on using the graph's spectra. This work has inspired numerous works on this and related problems using tools from random matrix theory, random graphs, "sum-of-squares" framework, convex optimization, and machine learning. In the first part, I will survey the history and some recent developments related to this problem. In the second part I will talk about some recent works on recovering planted bipartite graphs; this will be based on joint work with Rameesh Paul and Prasad Raghavendra.
Pravesh Kothari
Title: Matrix Concentration and Applications to Algorithms and Combinatorics
Abstract: I will discuss matrix concentration inequalities and their applications to algorithm design and extremal combinatorics. Applications will include graph sparsification, solving certain beyond-worst-case instances of constraint satisfaction problems, and extremal girth problems in combinatorics.
Vipul Arora
Title: Low Degree Testing over the Reals
Abstract: We study the problem of testing whether a function $f: \reals^n \to \reals$ is a polynomial of degree at most $d$ in the distribution-free testing model. Here, the distance between functions is measured with respect to an unknown distribution $D$ over $\reals^n$ from which we can draw samples. In contrast to previous work, we do not assume that $D$ has finite support.
We design a tester that given query access to $f$, and sample access to $D$, makes $\poly(d/\eps)$ many queries to $f$, accepts with probability $1$ if $f$ is a polynomial of degree $d$, and rejects with probability at least $2/3$ if every degree-$d$ polynomial $P$ disagrees with $f$ on a set of mass at least $\eps$ with respect to $D$.
Our result also holds under mild assumptions when we receive only a polynomial number of bits of precision for each query to $f$, or when $f$ can only be queried on rational points representable using a logarithmic number of bits. Along the way, we prove a new stability theorem for multivariate polynomials that may be of independent interest.
This is a joint work with Arnab Bhattacharyya, Esty Kelman, Noah Fleming, and Yuichi Yoshida, and appeared in SODA’23.
Ramprasad Saptharishi
Title: A higher-degree generalization of the Polischuk-Spielman Lemma
Abstract:
One of the cores of most PCP constructions is a particular lemma of Polischuk and Spielman that states that the following:
If A(x,y,z) is a polynomial of the form A_0(x,y) + z A_1(x,y), and suppose we are told that A_1(alpha, y) divides A_0(alpha, y) for many alphas, and A_1(x, beta) divides A_0(x, beta) for many betas. Then, A_1(x,y) divides A_0(x,y) as bivariate polynomials. In other words, A(x,y,z) has a factor of the form (z - Q(x,y))
A natural question is whether a higher degree generalization of this holds, where the z-degree in A is more than one. We show that a suitable generalization of the above hypothesis does yield a generalization. In this talk, we will see how to prove this statement using Newton iteration.
This generalization was used to extend the soundness analysis of the so-called "line-point low-degree test".
This is joint work with Prahladh Harsha, Mrinal Kumar and Madhu Sudan.
Piyush Srivastava
Title: A few isoperimetric inequalities
Abstract: We will survey a (non-representative) sample of isoperimetric
inequalities, their methods of proof, and their applications to the
analysis of sampling algorithms.
The two talks will be partly based on joint work with Hariharan
Narayanan and Amit Rajaraman.
Prerona Chatterjee
Title: Recent Progress in Algebraic Circuit Complexity
Abstract:
Algebraic Circuit Complexity deals with the question of how easy or hard it is to compute a given polynomial formally. The abundance of polynomials in computing makes this question naturally interesting. Moreover, when studied through the lens of algebraic circuits, this question leads to a rich theory that is intertwined with (boolean) complexity theory.
This journey, towards finding explicit polynomials that are hard to compute, has seen tremendous progress over the past decade or so. In this talk, we will survey some of the important milestones and take a look at what might lie ahead.