Partial tests, universal tests and decomposability
From MaRDI portal
(Redirected from Publication:2988902)
information-theoretic lower boundspartial testingproperty testingsunflower theoremsuniversal testing
Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)
Recommendations
Cites work
- (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 using ideal lattices
- Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP
- Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based
- scientific article; zbMATH DE number 1559544 (Why is no real title available?)
- 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
(13)- Proofs of proximity for context-free languages and read-once branching programs
- Non-interactive proofs of proximity
- An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity
- Proofs of proximity for context-free languages and read-once branching programs
- A hierarchy theorem for interactive proofs of proximity
- Zero-knowledge proofs of proximity
- 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?)
- A characterization of constant-sample testable properties
- A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification
- Distribution-free proofs of proximity
- Nearly optimal bounds for sample-based testing and learning of k-monotone functions
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)
