Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Theory of Computing Systems
Erschienen in: Theory of Computing Systems 1/2016

01.07.2016

A Self-Tester for Linear Functions over the Integers with an Elementary Proof of Correctness

Erschienen in: Theory of Computing Systems | Ausgabe 1/2016

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We present simple, self-contained proofs of correctness for algorithms for linearity testing and program checking of linear functions on finite subsets of integers represented as n-bit numbers. In addition we explore a generalization of self-testing to homomorphisms on a multidimensional vector space. We show that our self-testing algorithm for the univariate case can be directly generalized to vector space domains. The number of queries made by our algorithms is independent of domain size.
Vorheriger Artikel Complexity of Approximating CSP with Balance / Hard Constraints
Nächster Artikel The Update Complexity of Selection and Related Problems

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
Note that by repeating C at least 1/𝜖 times and outputting the majority answer, error probability ≤ 𝜖 can be achieved.
 
Literatur
1.
Babai, L., Fortnow, L., Lund, C.: Non-deterministic exponential time has two-prover interactive protocols. Comput. Complex. 1, 3–40 (1991)MathSciNetCrossRefMATH
2.
Bellare, M., Coppersmith, D., Håstad, J., Kiwi, M., Sudan, M.: Linearity testing over characteristic two. IEEE Trans. Inf. Theory 42(6), 1781–1795 (1996)CrossRefMATH
3.
Bellare, M., Goldwasser, S., Lund, C., Russell, A.: Efficient probabilistically checkable proofs and applications to approximations. In: Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing, pp 294–304 (1993)
4.
Ben-Sasson, E., Sudan, M., Vadhan, S., Wigderson, A.: Randomness-efficient low degree tests and short pcps via epsilon-biased sets. In: Proceedings of the Thirty-Fifth Annual ACM Symposium on the Theory of Computing, pp 612–621 (2003)
5.
Blum, M., Luby, M., Rubinfeld, R.: Self-testing/correcting with applications to numerical problems. JCSS 47, 549–595 (1993)MathSciNetMATH
6.
Blum, M., Kannan, S.: Designing programs that check their work. J. ACM 42(1), 269–291 (1995)CrossRefMATH
7.
8.
Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. JACM 45(4), 653–750 (1998)MathSciNetCrossRefMATH
9.
Hastad, J., Wigderson, A.: Simple analysis of graph tests for linearity and pcp. Random Struct. Algo. 22(2), 139–160 (2003)MathSciNetCrossRefMATH
10.
Kaufman, T., Litsyn, S., Xie, N.: Breaking the 𝜖-soundness bound of the linearity test over gf(2). Private Communications (2006)
11.
Kiwi, M.: Probabilistically Checkable Proofs and the testing of Hadamard-like codes. PhD thesis, Massachusetts Institute of Technology (1996)
12.
13.
Rubinfeld, R., Sudan, M.: Self-testing polynomial functions efficiently and over rational domains. In: Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms, pp 23–32 (1992)
14.
Rubinfeld, R., Sudan, M.: Robust characterization of polynomials with applications to program testing. SIAM J. Comput. 25(2), 252–271 (1996)MathSciNetCrossRefMATH
15.
Samorodnitsky, A., Trevisan, L.: A pcp characterization of np with optimal amortized query complexity. In: stoc00, pp 191–199 (2000)
16.
Samorodnitsky, A., Trevisan, L.: Gowers uniformity, influence of variables, and pcps. In: stoc06, pp 11–20 (2006)
17.
Shpilka, A., Wigderson, A.: Derandomizing homomorphism testing in general groups. In: Proceedings of the Thirty-Sixth Annual ACM Symposium on the Theory of Computing, pp 427–435 (2004)
18.
Sudan, M., Trevisan, L.: Probabilistically checkable proofs with low amortized query complexity. In: Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p 18 (1998)
19.
Trevisan, L.: Recycling queries in pcps and in linearity tests. In: Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, pp 299–308 (1998)
Metadaten
Titel
A Self-Tester for Linear Functions over the Integers with an Elementary Proof of Correctness
Publikationsdatum
01.07.2016
Erschienen in
Theory of Computing Systems / Ausgabe 1/2016
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI
https://doi.org/10.1007/s00224-015-9639-z

Weitere Artikel der Ausgabe 1/2016

Theory of Computing Systems 1/2016 Zur Ausgabe

OriginalPaper

Complexity of Approximating CSP with Balance / Hard Constraints

OriginalPaper

The Update Complexity of Selection and Related Problems

OriginalPaper

Holant Problems for 3-Regular Graphs with Complex Edge Functions

OriginalPaper

On the Stability of Generalized Second Price Auctions with Budgets

OriginalPaper

The Computational Complexity of Iterated Elimination of Dominated Strategies

OriginalPaper

On the Parameterised Complexity of String Morphism Problems