Высоковероятные k-мерные приближения булевых функций

Abstract

Булева функция от переменных называется k-мерной, если она линейно эквивалентна функции от переменных, . Основным результатом, представленным в докладе, является теорема о строении k-мерных функций степени , на расстоянии не более , от заданной булевой функции переменных. Эта теорема существенно усиливает известный результат П. Гопалана и позволяет предложить эффективный алгоритм построения всех указанных k-мерных булевых функций.