June 9, Wednesday
12:00 – 13:30
Optimal Base Problems
Graduate seminar
Lecturer : Yoav Fekete
Affiliation : CS,BGU
Location : 202/37
Host : Graduate Seminar
We define a simple mathematical problem which we call the optimal base problem:
Given a multiset S of positive integers, find a numeral base B such that the size of the representation of S in B is minimal.
For example if S={16,30,54,60} then in base 10 the sum of the digits is 25, while in base 2 it is 13, and in base 3 it is 12.
The problem gets more interesting when we allow mixed radix bases such as B=<3,5,2,2}
with respect to which the sum of the digits in S is only 9.
We analyze the complexity of this problem and propose a quasi-polynomial algorithm to solve it.
Our implementation improves significantly on existing techniques.
Finally we present also an application.
Joint work with Michael Codish, Carsten Fuhs and Peter Schneider-Kamp