Events

Constructing Elliptic Curve Isogenies in Quantum Subexponential Time

Abstract:

Given two elliptic curves over a finite field having the same cardinality and endomorphism ring, it is known that the curves admit an isogeny (a.k.a.

Branch-and-cut-and-price approaches to some combinatorial optimization problems

Abstract:

Dynamic column and cut generation are very important tools in integer programming.

Asymptotic enumeration of sparse 2-connected graphs and strongly connected digraphs

Abstract:

I will discuss an asymptotic formula for the number of 2-connected graphs on n vertices and m edges, provided that m-n→∞ and m=O(n log n) as n→∞

SDP Integrality Gaps for Constraint Satisfaction Problems, from Pairwise Independence

Abstract:

This work considers the problem of approximating fixed predicate constraint satisfaction problems (MAX k-CSP(P)).

Maximum Stirling Numbers of the Second Kind

Rota's Conjecture and nested separations in matroids

Abstract:

Rota's Conjecture is, possibly, the most famous open problem in matroid theory. We will discuss an interesting and useful partial result obtained with Shalev Ben-David.

Quantum query complexity of minor-closed graph properties

Abstract:

We study the quantum query complexity of minor-closed graph properties, which include such problems as determining whether a graph is planar, is a forest, or does not contain a path of a given length.

The Inverse Wronskian Problem, with a Twist

Abstract:

The inverse Wronskian problem is to find, for each polynomial $h(z)$, all vector spaces that are spanned by polynomials with Wronskian equal to $h(z)$.

Proof of the monotone column permanent conjecture

Abstract:

Let A be a square matrix of real numbers which are weakly decreasing down each column, let J be the all-ones matrix of the same size, and let z be an indeterminate.

Approximating Generalized Covering Integer Programs

Abstract:

Many network design problems are naturally cast as 0,1 (set-) covering integer programs, where connectivity requirements are expressed through cut-covering constraints; e.g., a set of edges is feasible if each edge-cut is covered by a s