# STCS Seminar

# 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.

# 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.

# 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

# Edit Distance Codes via Synchronization Strings

## Speaker:

## Organisers:

## Time:

## Venue:

I will describe a recent approach to designing codes that correct for "editing" errors - i.e., where an adversary is allowed to delete some of the symbols in a string being transmitted and insert new symbols. The classical Hamming model of errors

# Optimisation Using the D-Wave Adiabatic Quantum Computer

## Speaker:

## Organisers:

## Time:

## Venue:

Even though classical computers have evolved immensely in the past decades, there remain problems that we can never imagine solving on a classical computer in reasonable time.

# Improved NP-hardness of Hypergraph Rainbow Coloring

## Speaker:

## Organisers:

## Time:

## Venue:

## Webpage:

A k-uniform hypergraph is defined to be q-rainbow colorable (q\leq k) if there exists a coloring of the vertex set with q colors such that every hyperedge contains all the q colors.

# On Top Fan-in vs Formal Degree for Depth-3 Arithmetic Circuits

## Speaker:

## Organisers:

## Time:

## Venue:

A well known fact is that there are polynomials of degree 2 (for instance, inner product, or elementary symmetric polynomials of degree 2), such that any representation of these as a sum of product of affine forms requires Omega(n) summands, where

# Approximation and Inapproximability of Guarding Polygons

## Speaker:

## Organisers:

## Time:

## Venue:

The art gallery problem deals with determining the minimum number of guards (or cameras) that are sufficient to cover or see every point in the interior of an art gallery, assuming that the guards have 360° visibility and can see an unbounded dist

# Deterministic Factorization of Sparse Polynomials with Bounded Individual Degree

## Speaker:

## Organisers:

## Time:

## Venue:

We study the problem of deterministic factorization of sparse polynomials.