Fully Homomorphic Encryption (FHE) is a powerful tool in cryptography which has found diverse applications; from privacy preserving machine learning to secure delegated computation. In this talk, I will talk about the FHE construction from Learning With Error (LWE) proposed by Gentry, Sahai and Waters and how the ideas behind this construction lead to various primitives like Constrained Pseudorandom Function and Predicate Encryption.

List Decoding is a fundamental problem in coding theory that seeks to find codewords close to a received word. It is well known that unique decoding is possible as long as the number of errors is less than delta/2, where delta is the distance of the code. However, we are interested in the regime where the number of errors is at most delta-epsilon where epsilon greater than 0. In this setting, unique decoding is not possible, but we aim to find all possible codewords within this error radius, provided the list of solutions remains small. It has been shown that random linear codes achieve a constant list size of O(1/epsilon) leading to the natural conjecture that explicit codes might also attain this bound. In this talk, we will show that explicit Folded Reed-Solomon Codes, a variant of Reed-Solomon Codes, achieve this optimal list size, proving that they exhibit pseudorandom behavior.

In this talk we will see how to factorize bivariate polynomials where individual degree of each variable is 2. Then we will try to generalize that idea for multivariate polynomial and will come up with a randomized algorithm for factorizing algebraic circuit.

In this talk, I would like to go over the classic paper "Nearly-linear Size Holographic Proofs" by Alexander Polishchuk and Daniel Spielman in 1994. The proof of the main theorem makes use of an error-locating polynomial as we saw in the Berlekamp-Welch algorithm to decode Reed-Solomon code. Moreover, I plan to go over an approximated version of Polishchuk-Spielman, which I worked on its proof but did not end up being used in my paper. I will also talk about one application of Polishchuk-Spielman, which shows up in constructing PCP of Proximity by Eli Ben-Sasson and Madhu Sudan in 2005.

The covering problem can be represented by a linear program (see Covering problem). In this talk, I will introduce an simple online algorithm that computes a O(log n)-competitive feasible solution. (n is the number of variables).

We will discuss how finding the Tensor decomposition of Tensors is equivalent to proper learning of depth 3 set-multilinear arithmetic circuits and describe how to do it deterministically in time $2^{poly(k)}.poly(n,d)$ where $k$ is the rank of the input n-variate d dimensional Tensor. This is based on joint work with Vishwas Bhargava

In fair division, we have many algorithms for allocating goods when there are no restrictions on the possible bundles of goods that a person can receive. However, in constrained problems, such as shift allocations to nurses, we know much very little about how to achieve fair allocations. In this talk, we will go over known results and open questions regarding finding fair allocations under matroid constraints, a broad family of constraints that generalize many practical settings.

We consider the hash function h(x) = (ax + b mod p) mod m where a, b are chosen uniformly at random from {0, 1, . . . , p - 1} . We prove that when we use h(x) in hashing with chaining to insert n elements into a table of size n the expected length of the longest chain is Õ(n^1/3).

We consider the challenge of AI value alignment with multiple individuals that have different reward functions and optimal policies in an underlying Markov decision process. We formalize this problem as one of policy aggregation, where the goal is to identify a desirable collective policy. We argue that an approach informed by social choice theory is especially suitable. Our key insight is that social choice methods can be reinterpreted by identifying ordinal preferences with volumes of subsets of the state-action occupancy polytope. Building on this insight, we demonstrate that a variety of methods --- including approval voting, Borda count, the proportional veto core, and quantile fairness --- can be practically applied to policy aggregation. (Joint work with Parand Alizadeh Alamdari and Ariel Procaccia. NeurIPS 2024)

A graph stream is a stream of edge updates. In this talk, I will survey a few fundamental problems in the graph semi-streaming model and present useful techniques for solving them.

Today we talk about a fun topic in discrete math, the axiom of choice. We will introduce this mildly controversial axiom, prove some of the classic results it implies as well as take a look at some of its fun, more paradoxical conclusions.