# STCS Seminar

# Learning arithmetic circuits in the average case via lower bounds

## Speaker:

## Organisers:

## Time:

The problem of learning arithmetic circuits is the following: given a polynomial as a black box that is promised to have a small arithmetic circuit computing it, can we find this arithmetic circuit?

# Convex Set Disjointness, Distributed Learning of Halfspaces, and Linear Programming

## Speaker:

## Organisers:

## Time:

Distributed learning protocols are designed to train on distributed data without gathering it all on a single centralized machine, thus contributing to the efficiency of the system and enhancing its privacy.

# Forecasting and the complexity of randomized algorithms

## Speaker:

## Organisers:

## Time:

Randomness is a remarkably powerful tool in the design of algorithms. By giving algorithms the ability to use random bits and letting them err with some small probability, we can solve many computational problems with remarkable efficiency.

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