Carregant...
Carregant...

Vés al contingut (premeu Retorn)

Degree lower bounds of tower-type for approximating formulas with parity quantifiers

Autor
Atserias, A.; Dawar, A.
Tipus d'activitat
Article en revista
Revista
ACM transactions on computational logic
Data de publicació
2014-02-01
Volum
15
Número
1
Pàgina inicial
Article No. 6
DOI
https://doi.org/10.1145/2559948 Obrir en finestra nova
Projecte finançador
TIN2010-20967-C04-04
Repositori
http://hdl.handle.net/2117/26697 Obrir en finestra nova
URL
http://dl.acm.org/citation.cfm?id=2559948&CFID=316295191&CFTOKEN=11341755 Obrir en finestra nova
Resum
Kolaitis and Kopparty have shown that for any first-order formula with parity quantifiers over the language of graphs, there is a family of multivariate polynomials of constant-degree that agree with the formula on all but a 2(-Omega(n))-fraction of the graphs with n vertices. The proof bounds the degree of the polynomials by a tower of exponentials whose height is the nesting depth of parity quantifiers in the formula. We show that this tower-type dependence is necessary. We build a family of f...
Citació
Atserias, A.; Dawar, A. Degree lower bounds of tower-type for approximating formulas with parity quantifiers. "ACM transactions on computational logic", 01 Febrer 2014, vol. 15, núm. 1.
Paraules clau
Algorithms, Canonical labeling algorithm, Convergence laws, Gowers uniformity norm, Graphs, Logic, Parity quantifiers, Random graphs, Theory
Grup de recerca
ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals

Participants

Arxius