Events

Span programs and quantum query complexity

Abstract:

The general adversary bound is a lower bound on the number of input queries required for a quantum algorithm to evaluate a boolean function. We show that this lower bound is in fact tight, up to a logarithmic factor.

Efficiency of random search methods on huge-scale optimization problems

Abstract:

In this talk we discuss new methods for solving huge-scale optimization problems. For problems of this size, even the simplest full-dimensional vector operations are very expensive.

Sum-Product Problem: New Generalisations and Applications

Matroids, Diophantine equations, and decidability

Abstract:

For a field F we consider the problem of deciding whether or not a given matroid is representable over the field.

Asymptotics of Some Partition Functions

Abstract:

Some recent results on the asymptotic analysis of partitions of integers will be discussed. First however some history of such problems will be briefly surveyed.

Representing some non-representable matroids

Abstract:

A matroid consists of a finite set, together with a partition of its subsets into "dependent" and "independent" ones, subject to some axioms.

The master equality polyhedron

Abstract:

In this talk, we introduce the master equality polyhedron (MEP), which generalizes the master polyhedra of Gomory (1969).

Plumbing 101: How to Deal With a Small Cryptographic Leakage

Abstract:

In this talk I will formalize the notion of leakage attacks on iterated cryptosystems, in which the attacker can find (via physical probing, power measurement, or any other type of side channel) one bit of information about the intermed

Learning Submodular Functions

Abstract:

A central topic in computational learning theory is learning Boolean functions defined on the Boolean cube. We consider a less-studied problem: learning real-valued function on the Boolean cube.

Computing with Untrusted Quantum Apparatus

Abstract:

Quantum information processing offers the possibility of solving computational problems previously thought to be intractable, and of achieving cryptographic objectives previously thought to be impossible.