# STCS Seminar

# TO BE ANNOUNCED

## Speaker:

## Organisers:

## Time:

# Hardness Characterisations and Size-Width Lower Bounds for QBF Resolution

## Speaker:

## Organisers:

## Time:

This talk will start with an overview of the relatively young field of QBF proof complexity, explaining the QBF proof system QURes, and an assessment of existing lower bound techniques.

# An algebraic algorithm for minimizing linearly representable submodular functions

## Speaker:

## Organisers:

## Time:

## Venue:

A set function f on the subsets of a set E is called submodular if it satisfies a natural diminishing returns property: for any two subsets S \subseteq T \subseteq E and an element x outside T, we have f(T + x) - f(T) \leq f(S+x) - f(S).

# Mathematics of Neural Nets

## Speaker:

## Organisers:

## Time:

## Venue:

One of the paramount mathematical mysteries of our times is to be able to explain the phenomenon of deep-learning i.e training neural nets.

# Simple, Credible, and Approximately-Optimal Auctions

## Speaker:

## Organisers:

## Time:

## Webpage:

**Abstract: **We present a general framework, applicable to both truthful and non-truthful auctions, for designing approximately revenue-optimal mechanisms for multi-item additive auctions.

# A Largish Sum-of-squares Implies Circuit Hardness (and Derandomization)

## Speaker:

## Organisers:

## Time:

**Abstract: **We study the sum of squares (*SOS*) representation of polynomials, i.e. f = \sum_{i\in s} c_i f_i^2 , where c_i are field elements and f_i(x_1,\ldots,x_n) are polynomials.

# Approximating the Nash Social Welfare with Subadditive Valuations

## Organisers:

## Time:

**Abstract: **How should one divide $m$ goods between $n$ agents, given the utility each agent has when allocated a subset of goods?

# On Decision Tree Complexity of Boolean Functions

## Speaker:

## Organisers:

## Time:

Talk will be held on Zoom.

# Half-integral Duals, Connectivity Augmentation and Multiflows in Planar Graphs

## Speaker:

## Organisers:

## Time:

## Venue:

**Abstract: **Given an edge weighted graph and a spanning tree, $T$, the {\em tree augmentation problem} is to pick a minimum weight set of edges, $F$, such that $T\cup F$ is 2-edge connected. Williamson et.al.