Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: The Correct Exponent for the Gotsman-Linial Conjecture   We prove a new bound on the average sensitivity of polynomial threshold
functions. In particular we show that a polynomial threshold function of degree
$d$ in at most $n$ variables has average sensitivity at most
$\sqrt{n}(\log(n))^{O(d\log(d))}2^{O(d^2\log(d)}$. For fixed $d$ the exponent
in terms of $n$ in this bound is known to be optimal. This bound makes
significant progress towards the Gotsman-Linial Conjecture which would put the
correct bound at $\Theta(d\sqrt{n})$.

24
The categories of this paper are: dg-ga
11
The categories of this paper are: hep-lat
7
The categories of this paper are: hep-th
16
The categories of this paper are: stat
29
The categories of this paper are: funct-an
30
The categories of this paper are: q-alg
35
The categories of this paper are: mtrl-th
15
The categories of this paper are: nucl-ex
5
The categories of this paper are: gr-qc
0
The categories of this paper are: hep-ph
9
The categories of this paper are: nlin
25
The categories of this paper are: patt-sol
17
The categories of this paper are: q-fin
18
The categories of this paper are: econ
13
The categories of this paper are: quant-ph
8
The categories of this paper are: hep-ex