Date & Time: November 8, 2010; 16:30-17:30.
Venue: Ramanujan Hall
Speaker: Prof. Anand Srivastav, University of Kiel, Germany
Topic: Quantum-Evolutionary Computation of the Discrepancy of Arithmetic Progressions
Abstract: A celebrated result of Joel Spencer (1985) says that the discrepancy of a hypergraph on n nodes and n hyperedges iis at most 6n1/2 and the bound is tight for infitite families of hypergraphs. The fields medaillist Klaus Roth proved in 1964 for the hypergraph of arithmetic progressions on the first n integers that the the discrepancy of any 2-coloring is Ω(n1/4 ). Roth himself believed that this bound was too small and that the discrepancy actually should be close to n1/2 . This was disproved by S ́rk ̈zy (1974), who showed an a o 1/3 ). Inventing the partial coloring method, Beck (1981) showed upper bound of O((n log n) a nearly tight bound of O(n1/4 (log n)5/2 ). Finally Matouˇek and Spenceri (1996) solved s the discrepancy problem for by proving the asymptotically tight upper bound O(n1/4 ). From these results we now know that the minimum discrepancy for the graph of arithmetic progressions is of the asymptotic order n1/4 and the gap between the constants in Roth’s lower bound respective Matouˇek’s and Spencer’s upper bound is not very large. But s the algorithmically fundamental problem of computing a 2-coloring of discrepancy O(n1/4 ) remained unsolved.
The probabilistic method gives a randomized polynomial-time algorithm returning a 2-coloring of discrepancy at most O((n log(n))1/2 ) while the polynomial-time algorithm of S ́rk ̈zy can compute a O((n log n)1/3 ) discrepancy coloring. The central result of this paper a o is an algorithm based on quantum-evolutionary computation which is able to compute 2- colorings of the hypergraph of arithmetic progressions with by far the best discrepancy, outperforming the known algorithms experimentally, and which theoretically is never worse than the probabilistic method. We show that for the hypergraph of arithmetic progressions for n upto 30000, our algorithm is able to improve the best 2-coloring obtained by the algorithm of S ́rk ̈zy significantly.
a o This is joint work with C. Patvardhan (Dayalbagh Educational Institute, Agra) and V. Sauerland (Kiel).