# Past Events

# An Introduction to Chordal Graphs And Clique Trees

## Organisers:

## Time:

An undirected graph is chordal if every cycle of length greater than three has a chord: namely, an edge connecting two nonconsecutive vertices on the cycle. A clique of a graph $G$ is any maximal set of vertices that is complete in $G$. Let $G$

# Approximating a polynomial as a sum of simple polynomials

## Speaker:

## Organisers:

## Time:

In this talk, we will consider algorithmic problems which follow the following template: given a real-valued multivariate polynomial f(x) of degree d, is it approximately equal to a sum of a few "simple" polynomials, i

# Secure Multiparty Computation with Limited Connectivity

## Time:

Information theoretically secure multiparty computation (MPC) is a central primitive in modern cryptography.

# Hardness of Recognizing Geometric Intersection Graphs

## Speaker:

## Organisers:

## Time:

Many graph problems that are NP-hard for general graphs can be solved in polynomial time for planar graphs. We explore the domain of "almost" planar graphs. These are graphs that can be made planar by removing one or two vertices from them.

# Singularly Optimal Randomized Leader Election

## Speaker:

## Time:

This paper concerns designing distributed algorithms that are singularly optimal, i.e., algorithms that are simultaneously time and message optimal, for the fundamental leader election problem in networks.

# Algebraic Natural Proofs: the plot thickens

## Organisers:

## Time:

In the late 1990s, a paper by Razborov and Rudich pointed out a barrier towards proving boolean circuit lower bounds.

# Accelerating Black Box Estimation of Distribution Tails Using Self structuring Importance Samplers

## Organisers:

## Time:

Motivated by the increasing adoption of models which facilitate greater automation in risk management and decision-making, this talk presents a novel Importance Sampling (IS) scheme for estimating distribution tails for a rich class of objectives

# Formalizing Finite Set Combinatorics in Type Theory

## Organisers:

## Time:

Mathematical proofs when written in conventional ways often contain imprecise definitions, unstated background assumptions, and inferential gaps in reasoning.

# Off-policy evaluation in Reinforcement Learning using Linear Regression

## Organisers:

## Time:

In Reinforcement Learning, one often needs to evaluate a given policy using rewards observed by following another policy. This is called off-policy evaluation in Learning Theory parlance.