| Identifikační kód |
RIV/67985840:_____/19:00507746 |
| Název v anglickém jazyce |
Lower bounds on balancing sets and depth-2 threshold circuits |
| Druh |
D - Stať ve sborníku |
| Jazyk |
eng - angličtina |
| Vědní obor |
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8) |
| Rok uplatnění |
2019 |
| Kód důvěrnosti údajů |
S - Úplné a pravdivé údaje o výsledku nepodléhající ochraně podle zvláštních právních předpisů. |
| Počet výskytů výsledku |
2 |
| Počet tvůrců celkem |
4 |
| Počet domácích tvůrců |
1 |
| Výčet všech uvedených jednotlivých tvůrců |
Pavel Hrubeš (státní příslušnost: CZ - Česká republika, domácí tvůrce: A, vedidk: 6407862, orcid: 0000-0003-4526-4934, scopusid: 16052698100, researcherid: D-5439-2014)
S. Natarajan Ramamoorthy (státní příslušnost: US - Spojené státy americké)
A. Rao (státní příslušnost: US - Spojené státy americké)
A. Yehudayoff (státní příslušnost: IL - Stát Izrael) |
| Popis výsledku v anglickém jazyce |
There are various notions of balancing set families that appear in combinatorics and computer science. For example, a family of proper non-empty subsets S_1,...,S_k subset [n] is balancing if for every subset X subset {1,2,...,n} of size n/2, there is an i in [k] so that |S_i cap X| = |S_i|/2. We extend and simplify the framework developed by Hegedüs for proving lower bounds on the size of balancing set families. We prove that if n=2p for a prime p, then k >= p. For arbitrary values of n, we show that k >= n/2 - o(n). We then exploit the connection between balancing families and depth-2 threshold circuits. This connection helps resolve a question raised by Kulikov and Podolskii on the fan-in of depth-2 majority circuits computing the majority function on n bits. We show that any depth-2 threshold circuit that computes the majority on n bits has at least one gate with fan-in at least n/2 - o(n). We also prove a sharp lower bound on the fan-in of depth-2 threshold circuits computing a specific weighted threshold function. |
| Klíčová slova oddělená středníkem |
balancing sets;depth-2 threshold circuits;polynomials;majority;weighted thresholds |
| Stránka www, na které se nachází výsledek |
- |
| DOI výsledku |
10.4230/LIPIcs.ICALP.2019.72 |
| Odkaz na údaje z výzkumu |
- |