Programme of the DIAMANT symposium
Hotel Het Witte Huis, Soest
27 and 28 November 2014
Thursday  
11:0011:25  arrival and coffee  
11:2511:30  welcome  
Dmitry Feichtner 
Simplicial methods in Distributed Computing  
11:3012:25 
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:3014:00  lunch  
Kamiel Cornelissen (UT)  Smoothed Analysis of the Successive Shortest Path and MinimumMean Cycle Canceling Algorithms  
14:0014:25 
For minimumcost maximum flow (MCF) algorithms, worstcase 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 minimummean 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 worstcase 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 worstcase running time for dense graphs. We also show a lower bound of Omega(m^2*n*log phi). 

Junjiang Liu (UL)  On Padic Decomposable Form Inequalities  
14:3014:55 
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 padic 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)  Bitcommitment schemes with nonsignalling adversaries  
15:0015:25 
We consider multiprover bitcommitment 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 bitcommitment 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 nonsignalling. In this talk, we give an introduction to the nonsignalling 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 twoprover bitcommitment schemes. Joint work with Serge Fehr. 

15:3016:00  tea  
Albert Gunawan (UL)  Gauss composition on spheres  
16:0016: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 nonempty, 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  
16:3017:25 
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.
More precisely, for an ndimensional 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. 

17:3019.00  drinks  
19:00  dinner  
Friday  
Melanie Rieback (ROS)  Radically Open Security: Smashing the Stack for Fun and Nonprofit  
9:009:55  Radically Open Security is the world's first notforprofit 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 opensource, 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 (Sbox, OSAS).  
Rutger Kuyper (RUN)  Logic, computation and algebra: the Medvedev and Muchnik lattices  
10:0010: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 socalled “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 socalled '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:3011:00  coffee  
Djordjo Milovic (UL)  A generalization of a theorem of Friedlander and Iwaniec  
11:0011: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 2part of class groups of quadratic number fields.  
Gabriele Spini (CWI)  Linear Secret Sharing Schemes from Error Correcting Codes and Universal Hash Functions  
11:3011: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/2e (where e>0 is an arbitrary constant), having optimal share size. Joint work with R. Cramer, I. Damgaard, N. Doettling and S. Fehr.  
12:0013:30  lunch  
Weidong Zhuang (UL)  Reduced binary forms and root separation over function fields  
13:3013: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 nonzero 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 fields. 

Rob Eggermont (TUE)  Finiteness properties of congruence classes of infinite matrices  
14:0014:25  We look at spaces of infinitebyinfinite 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:3015:00  tea  
Marco Molinaro (TUD)  How Good Are Sparse CuttingPlanes?  
15:0015:55 
Sparse cuttingplanes are often the ones used in mixedinteger 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 cuttingplanes? 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 nonzero 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 cuttingplanes do not approximate the integer hull well. Finally, we show that using sparse cuttingplanes 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  