Invited speakers:

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).

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.

Marco Molinaro (TU Delft) - How Good Are Sparse Cutting-Planes?

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.

Contributed speakers:

Kamiel Cornelissen (UT) - Smoothed Analysis of the Successive Shortest Path and Minimum-Mean Cycle Canceling Algorithms

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).

Rob Eggermont (TUE) - Finiteness properties of congruence classes of infinite matrices

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.

Max Filliger (CWI) - Bit-commitment schemes with non-signalling adversaries

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.

Albert Gunawan (UL) - Gauss composition on spheres


Rutger Kuyper (RUN) - Logic, computation and algebra: the Medvedev and Muchnik lattices

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.

Junjiang Liu (UL) - TBA

Djordjo Milovic (UL) - TBA

Gabriele Spini (CWI) - Linear Secret Sharing Schemes from Error Correcting Codes and Universal Hash Functions

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.

Weidong Zhuang (UL) - TBA

Mathematics cluster DIAMANT

Upcoming events

NMC 2020 and Diamant symposium
14-4-2020 - 16-4-2020

News - more news

Call for PhD project proposals

NWO has issued a cluster-wide call for PhD project proposals. Researchers can apply if they are employed (i.e., hold a salaried position) at a Dutch university or a research institute recognised by NWO, and also have an appointment period for at least the duration of the application procedure and the entire duration of the research for which the grant is being applied for.

Read more.

ERC Starting Grant for Jesper Nederlof

Jesper Nederlof (TU/e) has been awarded an ERC Starting Grant of almost 1.5 ME. Nederlof will design faster algorithms for hard computational problems in computer science. The grant provides the researcher with the opportunity to further elaborate his own ideas during a period of five years.

Read more.

Full professor position in Discrete Mathematics in Delft

Delft Institute of Applied mathematics, Delft University of Technology, seeks a full Professor in the field of Discrete Mathematics. A description of the position can be found here. The deadline for applications is January 15, 2019.

ERC Starting grant for Daniel Dadush

Daniel Dadush (CWI) has been awarded an ERC Starting Grant of 1.5 ME for his proposal ‘Towards a Quantitative Theory of Integer Programming’. With this grant, Dadush aims to revolutionize the understanding of integer programming (IP), the most popular method used today for finding optimal solutions to real-world optimization problems.

Read more.