# Past Events

# Automated Analysis of Probabilistic Infinite-state Systems

## Speaker:

## Organisers:

## Time:

## Venue:

## Webpage:

I will survey the state of the art in the automated analysis of several classes of probabilistic infinite-state systems which naturally arise when studying probabilistic programs with recursive calls, queueing systems, population dynamics

# Ramanujan Graphs of All Degrees

## Speaker:

## Organisers:

## Time:

## Venue:

## Webpage:

We prove that there exist infinite families of bipartite Ramanujan graphs of every degree bigger than 2. We do this by proving a variant of a conjecture of Bilu and Linial about the existence of good 2-lifts of every graph.

# Workshop on Applications of Game Theory

## Time:

## Venue:

## Webpage:

In this day and a half event we start with a tutorial session on May 3 afternoon and conduct a workshop on May 4 where researchers from India working in diverse areas including economics, computer science, statistical physics and probabilistic mod

# Boolean Monotonicity Testing via an Isoperimetry Result on the Directed Hypercube

## Speaker:

## Organisers:

## Time:

## Venue:

## Webpage:

A Boolean function $f:\{0,1\}^n \to \{0,1\}$ is monotone if $f(x) \geq f(y)$ whenever $x > y$, that is, all coordinates of $x$ dominate those of $y$.

# Local Search for Computationally Hard Constraint Satisfaction Problems

## Speaker:

## Organisers:

## Time:

## Venue:

## Webpage:

Since the emergence of Artificial Intelligence (AI) as a new field of modern science and engineering about 6 decades ago, concerted efforts have been made on designing and developing expressively adequate languages to represent knowledge about re

# Bridging the Gap: From Non-determinism to Determinism in UL

## Speaker:

## Organisers:

## Time:

## Venue:

The class of Unambiguous Star-free regular languages over words has been variously characterized in the past by logics such as the fragments $\Delta_2[<]$ and $FO^2[<]$ of first-order definable languages, Unary Temporal Logic $TL[F,P]$ as we

# Fast Low Rank Approximation via Random Projections

## Organisers:

## Time:

## Venue:

Given an m x n matrix A, we define the rank-k approximation of A as a matrix B of same size and of rank at most k such that A and B are close in the Frobenius norm.

# A Survey on Uniform Hardness Amplification in NP

## Organisers:

## Time:

## Venue:

## Webpage:

We investigate the following question: If NP contains functions which are slightly hard to compute on average then does NP also contain function which is very hard to compute on average?

# A Model for Equilibrium in Some Service-provider User-set Interactions

## Speaker:

## Organisers:

## Time:

## Venue:

## Webpage:

We propose a model for interaction between an user-set (market) and a service-provider (firm) when the offered demand is sensitive to the offered Quality of Service.