Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Some Improvements to Total Degree Tests   A low-degree test is a collection of simple, local rules for checking the
proximity of an arbitrary function to a low-degree polynomial. Each rule
depends on the function's values at a small number of places. If a function
satisfies many rules then it is close to a low-degree polynomial. Low-degree
tests play an important role in the development of probabilistically checkable
proofs.
  In this paper we present two improvements to the efficiency of low-degree
tests. Our first improvement concerns the smallest field size over which a
low-degree test can work. We show how to test that a function is a degree $d$
polynomial over prime fields of size only $d+2$.
  Our second improvement shows a better efficiency of the low-degree test of
Rubinfeld and Sudan (Proc. SODA 1992) than previously known. We show concrete
applications of this improvement via the notion of "locally checkable codes".
This improvement translates into better tradeoffs on the size versus probe
complexity of probabilistically checkable proofs than previously known.

30
The categories of this paper are: q-alg
8
The categories of this paper are: hep-ex
31
The categories of this paper are: ao-sci
17
The categories of this paper are: q-fin
24
The categories of this paper are: dg-ga
7
The categories of this paper are: hep-th
36
The categories of this paper are: cmp-lg
28
The categories of this paper are: alg-geom
6
The categories of this paper are: astro-ph
26
The categories of this paper are: bayes-an
33
The categories of this paper are: plasm-ph
18
The categories of this paper are: econ
9
The categories of this paper are: nlin
12
The categories of this paper are: nucl-th
3
The categories of this paper are: physics
10
The categories of this paper are: q-bio