Пятница 29.10. Svyatoslav Gryaznov: "A variant of the VC-dimension with applications to depth-3 circuits"

[PDMI seminars]

Семинар по теории сложности вычислений

Тема: A variant of the VC-dimension with applications to depth-3 circuits
Место: Zoom
Время: 29.10.2021, 11:30
Докладчик: Svyatoslav Gryaznov

Abstract:
We introduce the following variant of the VC-dimension. Given S ⊆ {0, 1} and a positive integer d, we define U_d(S) to be the size of the largest subset I ⊆ [n] such that the projection of S on every subset of I of size d is the d-dimensional cube. We show that determining the largest cardinality of a set with a given Ud dimension is equivalent to a Turán-type problem related to the total number of cliques in a d-uniform hypergraph. This allows us to beat the Sauer-Shelah lemma for this notion of dimension. We use this to obtain several results on Σ_3^k-circuits, i.e., depth-3 circuits with top gate OR and bottom fan-in at most k:

* Tight relationship between the number of satisfying assignments of a 2-CNF and the dimension of the largest projection accepted by it, thus improving Paturi, Saks, and Zane (Comput. Complex. ’00).

* Improved Σ_3^3 -circuit lower bounds for affine dispersers for sublinear dimension. Moreover, we pose a purely hypergraph-theoretic conjecture under which we get further improvement.

This is a joint work with Peter Frankl and Navid Talebanfard.

[Dmitry M. Itsykson]

https://zoom.us/j/95294301096?pwd=dXJXOWtqcjVZcy9qdXZZUTNFRjl0UT09

--
Вы получили это сообщение, поскольку подписаны на группу "spb-complexity".
Чтобы отменить подписку на эту группу и больше не получать от нее сообщения, отправьте письмо на электронный адрес spb-complexit...@googlegroups.com.
Чтобы посмотреть обсуждение на веб-странице, перейдите по ссылке https://groups.google.com/d/msgid/spb-complexity/000000000000a3a81a05cf065206%40google.com.