Constructive relationships between algebraic thickness and normality

Joan Boyar, Magnus Gausdal Find

Publikation: Kapitel i bog/rapport/konference-proceedingKonferencebidrag i proceedingsForskningpeer review

Abstrakt

We study the relationship between two measures of Boolean functions; algebraic thickness and normality. For a function f, the algebraic thickness is a variant of the sparsity, the number of nonzero coefficients in the unique F2 polynomial representing f, and the normality is the largest dimension of an affine subspace on which f is constant. We show that for 0<ϵ<2 , any function with algebraic thickness n3−ϵ is constant on some affine subspace of dimension Ω(nϵ/2) . Furthermore, we give an algorithm for finding such a subspace. We show that this is at most a factor of Θ(√n) from the best guaranteed, and when restricted to the technique used, is at most a factor of Θ(√log n) from the best guaranteed. We also show that a concrete function, majority, has algebraic thickness Ω(2n1/6) .
OriginalsprogEngelsk
Titel20th International Symposium, FCT 2015, Gdańsk, Poland, August 17-19, 2015, Proceedings
RedaktørerA. Kosowski, I. Walukiewicz
ForlagSpringer
Publikationsdato2015
Sider106-117
ISBN (Trykt)978-3-319-22176-2
ISBN (Elektronisk)978-3-319-22177-9
DOI
StatusUdgivet - 2015
Begivenhed20th International Symposium on Fundamentals of Computation Theory - Gdansk, Polen
Varighed: 17. aug. 201519. aug. 2015
Konferencens nummer: 20

Konference

Konference20th International Symposium on Fundamentals of Computation Theory
Nummer20
LandPolen
ByGdansk
Periode17/08/201519/08/2015
NavnLecture Notes in Computer Science
Vol/bind9210
ISSN0302-9743

Emneord

  • Boolean functions
  • algebraic thickness
  • normality
  • majority function

Fingeraftryk

Dyk ned i forskningsemnerne om 'Constructive relationships between algebraic thickness and normality'. Sammen danner de et unikt fingeraftryk.

Citationsformater