This award seeks progress in new areas of computational geometry: specifically, collective behavior, sublinearity, hereditary structures, and low-entropy geometric algorithms. Recent work on multiagent agreement systems has revealed the great potential of a geometric approach to the subject. A new generating function, the "total s-energy", shows considerable promise for the study of consensus. A thorough investigation of this new device is the starting point of this project.
Geometric data tends to capture a vast amount of coherence and hence little entropy. The second part of this project looks at four instances of this phenomenon: Markov sources, hereditary complexity, sublinear computing, and self-improving geometric algorithms. In the first case, the data is generated by a Markov chain; in the second, it is presented within a larger structure that is given explicitly; in the third, the data is only accessible in limited amounts through random sampling; in the fourth, it comes from an unknown memoryless low-entropy distribution. In all cases, the objective is the same: to go beyond worst-case analysis and make room for a more realistic analytical framework.
