Programme of the DIAMANT symposium
Hotel Het Witte Huis, Soest
27 and 28 November 2014



11:00-11:25 arrival and coffee
11:25-11:30 welcome

Dmitry Feichtner-
Kozlov (U Bremen)

Simplicial methods in Distributed Computing
In this talk we will discuss the application of methods of combinatorial algebraic topology to theoretical distributed computing. We will introduce the formal simplicial concepts of a task and a protocol and illustrate it on some of the central tasks of distributed computing. Finally, we will present several theorems which connect topological properties of the associated structures with the computability issues of the related tasks. This is a report on a joint book project with Maurice Herlihy and Sergio Rajsbaum.
12:30-14:00 lunch
Kamiel Cornelissen (UT) Smoothed Analysis of the Successive Shortest Path and Minimum-Mean Cycle Canceling Algorithms
14:00-14:25 For minimum-cost maximum flow (MCF) algorithms, worst-case running time bounds do not always give a good indication for how the algorithms perform in practice. To model the performance on practical instances, we analyze two MCF algorithms, the successive shortest path (SSP) algorithm and the minimum-mean cycle canceling (MMCC) algorithm, in the framework of smoothed analysis. An adversary can specify the flow network and the edge capacities, but for the edge costs c_e the adversary can only specify density
functions f_e of maximum density phi, according to which the edge costs are drawn.

We show that in the smoothed setting the SSP algorithm only needs O(m*n*phi*(m + n*log n)) running time, in stark contrast to the worst-case running time. We also show almost tight lower bounds.

For the MMCC algorithm we show a smoothed running time of O(m^2*n^2*(n*log n + log phi)), which is better than the worst-case running time for dense graphs. We also show a lower bound of Omega(m^2*n*log phi).
Junjiang Liu (UL) On P-adic Decomposable Form Inequalities  
In this talk, I first present Thunder's work on the finiteness of the solutions to decomposable form inequalities, which was originally Schmidt's conjecture. Afterwards, I will talk about the effectivity of the finiteness condition for decomposable form inequalities and the p-adic generalization of Thunder's work. In the end, I will talk about getting better bounds for the error term in special cases.
Max Filliger (CWI) Bit-commitment schemes with non-signalling adversaries
15:00-15:25 We consider multi-prover bit-commitment schemes whose security is based on the assumption that the provers cannot communicate with each other. As Crepeau et al. pointed out, previous security proofs of such schemes make the implicit assumption that the provers are classical, i.e., they do not share an entangled quantum state. They showed that there are schemes that are secure against classical adversaries, but insecure in the quantum setting. They also showed that there are schemes which are secure even against entangled adversaries.

We examine in how far it is possible to base the security of bit-commitment schemes only on the assumption that the provers cannot communicate with each other, making no further computational or physical assumptions. Adversaries that are only bound by this constraint are called non-signalling. In this talk, we give an introduction to the non-signalling setting, summarize the positive and negative results we achieved so far and give a proof of our impossibility result for a simple yet natural class of two-prover bit-commitment schemes.

Joint work with Serge Fehr.
15:30-16:00 tea
Albert Gunawan (UL) Gauss composition on spheres
16:00-16:25 Gauss's theorem on the sum of 3 squares relates the number of primitive integer points on the sphere of radius the square root of n with the class number of some quadratic imaginary order. In 2011, Edixhoven sketched a different proof of Gauss's theorem by using an approach from arithmetic geometry. He used the action of the special orthogonal group on the sphere and gives a bijection between the set of SO_3(Z)-orbits of such points, if non-empty,  with the set of isomorphism classes of torsors under the stabilizer group. This set of torsors is a group,  isomorphic to the group of isomorphism classes of projective rank one modules over the ring Z[1/2,\sqrt{-n}], that gives an affine space structure on the set of SO_3(Z)-orbits on the sphere. In this talk, I will give an explicit method and an example of how this parallelogram law works.
Daniel Dadush (CWI) New Bounds for Curved Polyhedra via the Shadow Simplex Method

We study the simplex method over polyhedra satisfying certain "discrete curvature" lower bounds. At a high level, these enforce that the boundary always meets vertices at ``sharp'' angles.

As our main results, we give an improved (constructive) diameter bound over these polytopes, as well as a faster simplex based algorithm for linear optimization. As our main technical tool, we develop a new analysis and variant of the shadow simplex method. Our work builds and improves upon the results of Bonifas et al (SOCG 2012), Brunsch and Roglin (ICALP 2013), and Eisenbrand, Vempala (2014).

More precisely, for an n-dimensional polyhedron with m facets and curvature parameter 0 < delta < 1, we give a diameter bound of O(n^2(1+ ln(n/delta))/delta). For the class of polyhedra having totally unimodular constraint matrices, this implies an O(n^3 ln n) diameter bound. For linear optimization, given an initial feasible vertex, we show that an optimal vertex can be found using an expected O(n^3(1+ln(n/delta))/delta) simplex pivots, each requiring O(m n) time to compute. Furthermore, a first feasible solution can be found using O(m n^3(1+ln(n/delta))/delta) pivot steps.

This is joint work with Nicolai Hahnle (University of Bonn).

17:30-19.00 drinks
19:00 dinner
Melanie Rieback (ROS) Radically Open Security: Smashing the Stack for Fun and Non-profit
9:00-9:55 Radically Open Security is the world's first not-for-profit computer security consultancy company.  We're a collective of hackers who aim to disrupt the computer security market with our ideals - we give 90% of our profits to the NLnet Foundation, work with volunteers, release all our tools/templates into the open-source, invite customers to actively participate in pentest teams, and generally optimize for openness, transparency, and community service.  This talk will discuss our unconventional business model and highlight some of our currently running research projects (S-box, OSAS).
Rutger Kuyper (RUN) Logic, computation and algebra: the Medvedev and Muchnik lattices
10:00-10:25 There are several ways to connect logic and computation, among which are the Medvedev and Muchnik lattices. Based on an informal idea of Kolmogorov, these algebraic structures were introduced using the machinery of computability theory and were an attempt to capture intuitionistic propositional logic (IPC) from a computational perspective (all from a classical point of view).

Intuitionistic logic is a logic formalised by Heyting, based on Brouwer's programme of intuitionism. Roughly speaking, intuitionistic logic is what one obtains if one drops the so-called “law of excluded middle", stating that for every statement P either P holds or P does not hold, from classical logic.

In this talk I will introduce the Medvedev and Muchnik lattices. These algebraic structures are so-called 'Brouwer algebras', which are structures that have a naturally associated propositional theory between IPC and classical logic. It turns out that, unfortunately, the theory associated with the Medvedev and Muchnik lattices is not IPC. Nevertheless, quite remarkably it turns out that this deficiency can be repaired by taking quotients, a fact first proven by Skvortsova. However, the quotient given by Skvortsova’s proof is not very natural. I will discuss recent improvements of her result which do give natural factors of the Medvedev and Muchnik lattices with associated theory IPC.
10:30-11:00 coffee
Djordjo Milovic (UL) A generalization of a theorem of Friedlander and Iwaniec
11:00-11:25 Friedlander and Iwaniec developed a sieve which allowed them to count primes of the form $a^2+c^4$. We will introduce this sieve and explain how to apply it to the problem of counting primes of the form $a^2+c^4$ with $a$ and $c$ satisfying certain congruence conditions. This result has applications in the study of the 2-part of class groups of quadratic number fields.
Gabriele Spini (CWI) Linear Secret Sharing Schemes from Error Correcting Codes and Universal Hash Functions
11:30-11:55 We present a novel method for constructing linear secret sharing schemes (LSSS) from linear error correcting codes and linear universal hash functions in a blackbox way. The main advantage of this new construction is that the privacy threshold of the resulting scheme becomes essentially independent of the code we use, only depending on its rate; this allows us to fully harness the algorithmic properties of recent code constructions such as efficient encoding and decoding or efficient list decoding. We present two constructions implementing this paradigm: a linear ramp secret sharing scheme with linear time sharing and reconstructions algorithms, allowing secrets of size linear in n; and an efficient robust secret sharing scheme for any fraction of dishonest players smaller than 1/2-e (where e>0 is an arbitrary constant), having optimal share size. Joint work with R. Cramer, I. Damgaard, N. Doettling and S. Fehr.
12:00-13:30 lunch
Weidong Zhuang (UL) Reduced binary forms and root separation over function fields
13:30-13:55 Over number field, two binary forms (i.e., homogeneous polynomials) F,G\in Z[X,Y] are called equivalent if G(X,Y)=F(aX+bY,cX+dY) for some matrix (a,b\\c,d)\in GL(2,Z), thereby sharing the same discriminant. A binary form F is called reduced if its height H(F) (maximum of the absolute values of its coefficients) is minimal among the heights of its equivalent class. It is conjectured that the height H(F) of a reduced binary form F of degree n\geq 4 and non-zero discriminant D has an upper bound of the form c_1(n)|D|^{c_2(n)}. I will explain my effective analogous result over k[t], where k is an algebraically closed field of characteristic 0, and then its application to the root separation problem, i.e., to bound from below the minimal distance of the roots of a given polynomial, thereby proving a function field analogue of Yann Bugeaud's conjecture over number
Rob Eggermont (TUE) Finiteness properties of congruence classes of infinite matrices
14:00-14:25 We look at spaces of infinite-by-infinite matrices, and consider closed subsets that are stable under simultaneous row and column operations. We prove that up to symmetry, any of these closed subsets is defined by finitely many equations.
14:30-15:00 tea
Marco Molinaro (TUD) How Good Are Sparse Cutting-Planes?
15:00-15:55 Sparse cutting-planes are often the ones used in mixed-integer programing (MIP) solvers, since they help in solving the linear programs encountered during branch-&-bound more efficiently. However, how well can we approximate the integer hull by just using sparse cutting-planes? In order to understand this question better, given a polyope P (e.g. the integer hull of a MIP), let P^k be its best approximation using cuts with at most k non-zero coefficients. We consider d(P, P^k) =  max_{x in P^k} (min_{y in P} |x - y|) as a measure of the quality of sparse cuts.

In our first result, we present general upper bounds on d(P, P^k) which depend on the number of vertices in the polytope and exhibits three phases as k increases. Our bounds imply that if P has polynomially many vertices, using half sparsity already approximates it very well. Second, we present a lower bound on d(P, P^k) for random polytopes that show that the upper bounds are quite tight. Third, we show that for a class of hard packing IPs, sparse cutting-planes do not approximate the integer hull well. Finally, we show that using sparse cutting-planes in extended formulations is at least as good as using them in the original polyhedron, and give an example where the former is actually much better.

Joint work with Santanu Dey and Qianyi Wang.
16:00 end of the symposium


Mathematics cluster DIAMANT

Upcoming events

NMC / Diamant symposium
3-4-2018 - 5-4-2018

News - more news

3 DIAMANT PhD positions awarded

NWO, following a shortlist provided by the DIAMANT board, has decided to award 3 PhD positions to young DIAMANT members: Dion Gijswijt (TU Delft), Jan Steffen Müller (RUG) and Arno Kret (UvA).
Read more.

DIAMANT funding continued

The funding of all four mathematics clusters has been continued by NWO. For the coming two years 85 kE will be available in each cluster.
Read more.

NWO Call for Tenure Track positions

NWO has opened a call for tenure track positions. Proposals for these positions, which include one PhD position for each tenure track position, can be submitted directly to NWO by professors from the 4 mathematics clusters, including Diamant. Diamant professors are warmly encouraged to submit proposals. Read more.

Dion Gijswijt and Jordan Ellenberg independently substantially improve capset bound

A capset in a finite dimensional vector space over the field with 3 elements is a subset that contains no 3-term arithmetic progressions. Dion Gijswijt (TU Delft) and Jordan Ellenberg have independently obtained a bound on the size of a capset that for the first time improves substantially on the trivial bound 3^n. Read more in Terence Tao's blog about these developments.