One of the famous open problems in randomized query complexity is the composition question: Is R(f o g) = Omega(R(f)R(g)) for all boolean functions f and g.
Karl Weierstrass showed that given a continuous function $f$ on $[0,1]$ and an epsilon positive, there is a polynomial $p$ such that it is uniformly epsilon close to $f$ on $[0,1]$.
In this talk we will see an efficient parallel algorithm for the Bipartite Perfect Matching problem (BPM) due to Fenner, Gurjar and Thierauf. The Perfect Matching problem (PM) is to decide whether a given graph has a perfect matching.
Let X_1, X_2, ... ,X_n be, possibly dependent, [0,1]-valued random variables. The following question is important: What is a sharp upper bound on the probability that their sum is significantly larger (or significantly smaller) than their mean?
Musical sounds and their compositions can be analysed and synthesised using digital signal processing techniques. Computers are now increasingly used in editing, processing and even synthesis of music.
The general Art Gallery Problem (AGP) consists in finding the minimum number of guards sufficient to ensure the visibility coverage of an art gallery represented by a polygon.
We are in the midst of a major data revolution. The total data generated by humans from the dawn of civilization until the turn of the new millennium is now being generated every two days.
