DOI

In this paper we motivate the study of Boolean dispersers for quadratic varieties by showing that an explicit construction of such objects gives improved circuit lower bounds. An (n; k; s)-quadratic disperser is a function on n variables that is not constant on any subset of Fn2 of size at least s that can be defined as the set of common roots of at most k quadratic polynomials. We show thfi at if a Boolean function f is a n; 1:83n; 2g(n)-quadratic disperser for any function g(n) = o(n) then the circuit size of f is at least 3:11n. In order to prove this, we generalize the gate elimination method so that the induction works on the size of the variety rather than on the number of variables as in previously known proofs.

Язык оригиналаанглийский
Название основной публикацииITCS 2016 - Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science
ИздательAssociation for Computing Machinery
Страницы405-411
Число страниц7
ISBN (электронное издание)9781450340571
DOI
СостояниеОпубликовано - 14 янв 2016
Событие7th ACM Conference on Innovations in Theoretical Computer Science, ITCS 2016 - Cambridge, Соединенные Штаты Америки
Продолжительность: 14 янв 201616 янв 2016

Серия публикаций

НазваниеITCS 2016 - Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science

конференция

конференция7th ACM Conference on Innovations in Theoretical Computer Science, ITCS 2016
Страна/TерриторияСоединенные Штаты Америки
ГородCambridge
Период14/01/1616/01/16

    Предметные области Scopus

  • Теоретические компьютерные науки
  • Компьютерные науки (все)

ID: 49824036