Aktiviteter pr. år
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 F_{2} 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 n^{3−ϵ} 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 Ω(2^{n1/6}) .
Originalsprog  Engelsk 

Titel  20th International Symposium, FCT 2015, Gdańsk, Poland, August 1719, 2015, Proceedings 
Redaktører  A. Kosowski, I. Walukiewicz 
Forlag  Springer 
Publikationsdato  2015 
Sider  106117 
ISBN (Trykt)  9783319221762 
ISBN (Elektronisk)  9783319221779 
DOI  
Status  Udgivet  2015 
Begivenhed  20th International Symposium on Fundamentals of Computation Theory  Gdansk, Polen Varighed: 17. aug. 2015 → 19. aug. 2015 Konferencens nummer: 20 
Konference
Konference  20th International Symposium on Fundamentals of Computation Theory 

Nummer  20 
Land  Polen 
By  Gdansk 
Periode  17/08/2015 → 19/08/2015 
Navn  Lecture Notes in Computer Science 

Vol/bind  9210 
ISSN  03029743 
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.Relaterede Aktiviteter
 1 Foredrag og præsentationer i privat eller offentlig virksomhed

Constructive relationships between algebraic thickness and normality
Joan Boyar (Foredragsholder)
17. aug. 2015Aktivitet: Foredrag og mundtlige bidrag › Foredrag og præsentationer i privat eller offentlig virksomhed