kth.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Simple analysis of graph tests for linearity and PCP
KTH, Superseded Departments (pre-2005), Numerical Analysis and Computer Science, NADA.ORCID iD: 0000-0002-5379-345X
2003 (English)In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 22, no 2, p. 139-160Article in journal (Refereed) Published
Abstract [en]

We give a simple analysis of the PCP with low amortized query complexity of Samorodnitsky and Trevisan [16]. The analysis also applies to the linearity testing over finite fields, giving a better estimate of the acceptance probability in terms of the distance of the tested function to the closest linear function.

Place, publisher, year, edition, pages
2003. Vol. 22, no 2, p. 139-160
Keywords [en]
linearity testing, PCP, graph test, iterated test, pseudorandomness, hardness, proofs
Identifiers
URN: urn:nbn:se:kth:diva-22270DOI: 10.1002/rsa.10068ISI: 000181119600001Scopus ID: 2-s2.0-0242299157OAI: oai:DiVA.org:kth-22270DiVA, id: diva2:340968
Note
QC 20100525Available from: 2010-08-10 Created: 2010-08-10 Last updated: 2022-06-25Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Håstad, Johan

Search in DiVA

By author/editor
Håstad, Johan
By organisation
Numerical Analysis and Computer Science, NADA
In the same journal
Random structures & algorithms (Print)

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 95 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf