Bodo Manthey, RĂ¼diger Reischuk

Binary search trees are one of the most fundamental data structures. While the

height of such a tree may be linear in the worst case, the average height with

respect to the uniform distribution is only logarithmic. The exact value is one

of the best studied problems in average case ...
more >>>

Xi Chen, Xiaotie Deng, Shang-Hua Teng

By proving that the problem of computing a $1/n^{\Theta(1)}$-approximate Nash equilibrium remains \textbf{PPAD}-complete, we show that the BIMATRIX game is not likely to have a fully polynomial-time approximation scheme. In other words, no algorithm with time polynomial in $n$ and $1/\epsilon$ can compute an $\epsilon$-approximate Nash equilibrium of an $n\times ... more >>>

Bodo Manthey, Till Tantau

Binary search trees are a fundamental data structure and their height

plays a key role in the analysis of divide-and-conquer algorithms like

quicksort. Their worst-case height is linear; their average height,

whose exact value is one of the best-studied problems in average-case

complexity, is logarithmic. We analyze their smoothed height ...
more >>>

Adam Klivans, Raghu Meka

We give a new framework for proving the existence of low-degree, polynomial approximators for Boolean functions with respect to broad classes of non-product distributions. Our proofs use techniques related to the classical moment problem and deviate significantly from known Fourier-based methods, which require the underlying distribution to have some product ... more >>>

tatsuie tsukiji

This paper aims to derandomize the following problems in the smoothed analysis of Spielman and Teng. Learn Disjunctive Normal Form (DNF), invert Fourier Transforms (FT), and verify small circuits' unsatisfiability. Learning algorithms must predict a future observation from the only $m$ i.i.d. samples of a fixed but unknown joint-distribution $P(G(x),y)$ ... more >>>