Arithmetic circuits are a model of computation that captures the computation of polynomials. Reconstruction/Learning is the problem of given black-box access to an input circuit, outputting a circuit that computes the same polynomial as the input one.We will discuss some properties of Arithmetic circuits, what makes them interesting, connections and hardness of Reconstruction, and, if time permits, how to reconstruct depth-3 circuits with small top fan-in. This is based on my recent work with Shubhangi Saraf.

In this talk I will talk about our recent work on differentially private online query release. We give the first online algorithm that is log-competitive to the offline factorization mechanism. I will cover the overall structure of our algorithm and go into some proofs.

In the 80's Kaltofen and Trager designed an efficient polynomial factorization algorithm with an oracle access to Polynomial Identity testing (PIT) which is well known to have a randomized algorithm. Recently the breakthrough result by Limaye, Srinivasan and Tavenas [LST 21] lead to a deterministic subexponential identity testing for polynomials computed by constant-depth arithmatic circuits. However this will not directly imply an subexp deterministic factorization for constant depth-circuits for some technical reasons. In this talk I will discuss how we can even derandomize the factorization algorithm for constant depth circuits from [LST 21]. The main tool for this work is an application of Newton iterarion which is inspired from a work of Chou, Kumar and Solomon [CKS 18]. This is a joint work with Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi and Shubhangi Saraf.

The concept of market equilibrium is one of the most powerful tools we have in the field of fair division, as equilibrium allocations are known to give very strong fairness and efficiency guarantees. Under a broad class of fair division instances, it is known that market equilibrium allocations always exist through a reduction to a fixed-point theorem. However, this existence result does not directly help us find the desired allocation, since fixed points are computationally difficult to compute in general. In the particularly important special case of fair division with linear utilities, we can in fact find equilibrium allocations efficiently. We will examine the seminal Eisenberg–Gale convex program and prove the surprising fact that the allocation that maximizes the product of agents’ utilities (commonly known as the Maximum Nash Welfare allocation) always corresponds to a Fisher market equilibrium from equal incomes.

In this talk, we will see the concept of “right kernelizing” Sudan’s algorithm and its consequences. In particular, we will examine how to decode interleaved Reed-Solomon codes under random errors and surpass the Johnson bound under certain parameter regimes. Interleaved Reed-Solomon codes were crucial in developing Parvaresh-Vardy codes, which led to Folded Reed-Solomon codes that can be decoded from capacity in nearly linear time. By the end of the talk, I hope your appreciation for Sudan’s algorithm will increase even more.

TBD

TBD

TBD

TBD

TBD