Partial tests, universal tests and decomposability

DOI10.1145/2554797.2554841MaRDI QIDQ2988902zbMATH OpenOpenAlexFDO

Authors Eldar Fischer, Yonatan Goldhirsh, Oded Lachish

Publication date 19 May 2017

Published in Proceedings of the 5th conference on Innovations in theoretical computer science (Search for Journal in Brave)

Full work available at URL https://eprints.bbk.ac.uk/id/eprint/13241/1/advice.pdf

zbMATH Keywords

property testinginformation-theoretic lower boundspartial testingsunflower theoremsuniversal testing

Mathematics Subject Classification ID

Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Recommendations

• Property testing lower bounds via communication complexity
• On Proximity-Oblivious Testing
• On proximity oblivious testing
• Testing of matrix properties
• Tolerant versus intolerant testing for Boolean properties

Cites work

• scientific article; zbMATH DE number 1559544 (Why is no real title available?)
• (Leveled) fully homomorphic encryption without bootstrapping
• A hierarchy of polynomial time lattice basis reduction algorithms
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Bounds for Width Two Branching Programs
• Efficient Fully Homomorphic Encryption from (Standard) LWE
• Evaluating Branching Programs on Encrypted Data
• Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP
• Fully homomorphic encryption using ideal lattices
• Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based
• New lattice-based cryptographic constructions
• On lattices, learning with errors, random linear codes, and cryptography
• On lattices, learning with errors, random linear codes, and cryptography
• Pseudorandom knapsacks and the sample complexity of LWE search-to-decision reductions
• Public-key cryptosystems from the worst-case shortest vector problem
• Toward basing fully homomorphic encryption on worst-case hardness
• Trapdoors for hard lattices and new cryptographic constructions
• Trapdoors for lattices: simpler, tighter, faster, smaller

Cited in

(11)

• An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity
• Zero-knowledge proofs of proximity
• Proofs of proximity for context-free languages and read-once branching programs
• Non-interactive proofs of proximity
• A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification
• A hierarchy theorem for interactive proofs of proximity
• Proofs of proximity for context-free languages and read-once branching programs
• A characterization of constant-sample testable properties
• Proofs of proximity for distribution testing
• An exponential separation between MA and AM proofs of proximity
• scientific article; zbMATH DE number 7250162 (Why is no real title available?)

This page was built for publication: Partial tests, universal tests and decomposability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2988902)