Arithmetic circuits give us a model of computation that captures algebraic methods and allows us to use, and even extend tools, developed in Maths. A major reason for studying them also comes from the added algebraic structure in this model compared to their Boolean counterparts. In this talk, we will discuss some results where we are able to reduce the depth required for arithmetic circuits(even to depth3). We will mainly focus on a classic result (Valiant, Skyum, Berkowitz, Rackoff83) that for a degree d polynomial that can be computed by a size s circuit, gives a depth O(log d) arithmetic circuit of size poly(sd).

Imagine a store that wants to sell a set of goods to a set of agents. Each agent has a budget they can spend, and a utility function over the goods. When they enter the store, they will attempt to buy the bundle of goods within their budget that maximizes their utility. Are there prices the store can assign to each good so that the sum of the goods demanded by the agents exactly equals the supply of goods that the store has available? When such a set of prices does exist, they are said to induce equilibrium in the market. In this talk, I will give an introduction to General Equilibrium Theory, going over some classic results about existence of equilibrium prices. I will also discuss why the field is important to both economists and computer scientists, and its implications for the field of fair division.

Secure multiparty computation (MPC) is a subfield of cryptography. I will discuss the MPC protocol by Beaver, Micali, and Rogaway [BMR90]. For simplicity, we will focus on the two-party case. At the same time, we will show that the secure evaluation of an arbitrary function f can be reduced to the secure evaluation of degree-3 polynomials. This idea is generalized by Ishai and Kushilevitz, who refer to it as "randomizing polynomials" [IK00]. No prior knowledge of cryptography is required. (P.S. We do TSS at the end of a long day of hard work, so my goal is to make this as easy as possible for both the audience and myself.)

In this talk, we will look at a relatively new algorithmic framework based on continuous optimization and regularization for discrepancy minimization introduced by Pesenti and Vladu. I will outline their simple and elegant techniques and recover the classic Spencer's theorem.

In this talk, I will talk about the influence of coalitions. At a high level, the influence of a coalition on a particular voting rule is the probability that the coalition can force the outcome of an election to their desired outcome by manipulating their votes. There is naturally a tradeoff between the coalition’s size and its influence, and we will focus on this. I'll discuss what is known, about this problem, and highlight a work of Bourgain, Kahn, and Kalai of 2014 which studies the influence of linear sized coalitions on random CNFs. I'll conclude by stating some interesting open questions and the relationship between this problem and a problem that I am working on in projections. If this abstract sounds familiar, it might be because I gave a TSS on a famous lower bound (KKL) for the influence of \emph{individuals} last year.

In this talk, we will discuss the recent greedy approach for determining the rank of matrices whose entries are linear polynomials in commutative and non-commutative models, and further generalize this method to partially commutative setting. This approach forms the key idea used in [Ivanyos, Qiao, Subrahmanyam 2016] (for non-commutative rank computation), [Blaser, Jindal, Pandey 2017], [Bhargava, Blaser, Jindal, Pandey 2018] (for commutative rank approximation), and [Arvind, Chatterjee, Mukhopadhyay 2024] (for partially commutative rank computation).

I will do a recap on DP then I will introduce the factorization mechanism with some example algorithms.

Tensors, or equivalently multilinear forms have intimate relations to central problems in computer science and combinatorics. The complexity of matrix multiplication is captured by the rank of the matrix multiplication tensor. In arithmetic complexity, proving super-linear lower bounds for tensors is related to proving lower bounds for arithmetic circuits and formulas. A different notion of rank, analytic rank, was introduced by Gowers and Wolf in the context of higher-order Fourier analysis. In this talk we use this concept to prove the common roots of order-d tensors on a common input are always positively correlated.

Traditional analyses of differentially private gradient descent assume that each iteration of gradient descent publicly releases intermediate configurations, causing privacy cost to scale linearly with the number of iterations. We present an older work of Feldman, Mironov, Talwar, and Thakurta (2018) that, through a Renyi-DP analysis, shows that only outputting the final configuration (of model weights, regression parameters, etc.), we can obtain sub-linear privacy cost for gradient descent. If time permits, we may discuss work that builds on this result showing that under certain conditions, privacy costs converge even with an unbounded number of training iterations.

Private information retrieval (PIR) protocols, a cryptographic model defined by Chor, Goldreich, Kushilevitz, and Sudan at FOCS 1995, allows a client to retrieve an element from a database held by multiple servers, without revealing the index of the retrieved item. Over the last three decades, PIR protocols have been extensively studied, and many constructions, variants, and applications of PIR protocols were presented. In this talk I will discuss simple constructions of PIR protocols and connections between PIR protocols and other cryptographic primitives.

In this paper, we construct Error-Correcting Graph Codes. An error-correcting graph code of distance δ is a family C of graphs on a common vertex set of size n, such that if we start with any graph in C, we would have to modify the neighborhoods of at least δn vertices in order to obtain some other graph in C. This is a natural graph generalization of the standard Hamming distance error-correcting codes for binary strings. Yohananov and Yaakobi were the first to construct codes in this metric, constructing good codes for δ less than 1/2, and optimal codes for a large-alphabet analogue. We extend their work by showing a.) Combinatorial results determining the optimal rate vs. distance trade-off nonconstructively. b.) Graph code analogues of Reed-Solomon codes and code concatenation, leading to positive distance codes for all rates and positive rate codes for all distances. c.) Graph code analogues of dual-BCH codes, yielding large codes with distance δ = 1 − o(1). This gives an explicit “graph code of Ramsey graphs”.

TBD