# Past Events

# On the Probabilistic Degree of OR Over The Reals

## Organisers:

## Time:

## Venue:

A probabilistic polynomial is like a randomized algorithm. It is a distribution on polynomials such that, for each input, the probabilistic polynomial computes the function exactly with high probability.

# Improved Strong Upper Bounds for Policy Iteration

## Speaker:

## Organisers:

## Time:

## Venue:

**Abstract: **Markov Decision Problems (MDPs) are a well-studied abstraction of sequential decision making. Policy Iteration (PI) is a classical, widely-used family of algorithms to compute an optimal policy for a given MDP.

# Pseudo-deterministic Algorithms

## Speaker:

## Organisers:

## Time:

## Venue:

In this talk, we describe a new type of probabilistic algorithm (introduced by Gat and Goldwasser [GG11]) called Pseudo-deterministic Algorithms: a randomized algorithm which is guaranteed to run in expected polynomial time and to produce a correc

# Chance Encounters: Random Walks in Science

## Speaker:

## Time:

## Venue:

The element of chance enters not only in our daily affairs, but also in practically every branch of science. This lecture will discuss both aspects.

# Topology, Knowledge, Belief and Their Logics

## Speaker:

## Organisers:

## Time:

## Venue:

Abstract: We shall discuss the logical interpretation of Topology and Topological interpretations of various Logics.

# Spencer's Proof of a Random Greedy Packing

## Organisers:

## Time:

## Venue:

We will prove the following theorem which gives an alternate proof to the Erdős-Hanani conjecture.

# Quadratic Loss Minimization with Portfolio and Intertemporal Wealth Constraints

## Speaker:

## Organisers:

## Time:

## Venue:

We address a problem of stochastic optimal control motivated by portfolio optimization in mathematical finance, the goal of which is to minimize the expected value of a general quadratic loss function of the wealth at close of trade when there is

# On the Weakness of Linear Decision Lists

## Organisers:

## Time:

## Venue:

Abstract:

We consider functions computable efficiently by "linear decision lists", which are decision lists where the queries are linear threshold functions.

# On Randomization and Combinatorics in Computational Geometry, Discrete Mathematics, and Combinatorial Representation Theory.

## Speaker:

## Organisers:

## Time:

## Venue:

**Abstract:** In this talk we shall see three very different areas of applications of combinatorics in mathematics and computer science, illustrating different flavours of combinatorial reasoning.