We examine gradient descent on unregularised logistic regression problems, with homogeneous linear predictors on linearly separable datasets. We show the predictor converges to the direction of the max-margin (hard margin SVM) solution.

We will introduce the notion of determinantal complexity, one of the main characters in the VP vs VNP question, which is the algebraic analogue of the P vs NP question.

In the composite hypothesis testing setting, the detector receives n i.i.d. samples either from a distribution  p∈P or from a distribution q∈Q. It then decides the correct set from which the samples were drawn.

What is the largest number of edges in a graph of order n and girth g? For d-regular graphs, essentially the best known answer is provided by the Moore bound. This result can be extended to cover irregular graphs as well.

Quantum computers are in general believed to be more powerful than classical computers, but it is not clear if they are powerful enough to solve problems that a classical computer can’t even verify.