Partial tests, universal tests and decomposability
DOI10.1145/2554797.2554841zbMATH Open1364.68210OpenAlexW2160856947MaRDI QIDQ2988902FDOQ2988902
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
Recommendations
property testinginformation-theoretic lower boundspartial testingsunflower theoremsuniversal testing
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)
Cites Work
- A hierarchy of polynomial time lattice basis reduction algorithms
- Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP
- Evaluating Branching Programs on Encrypted Data
- Fully homomorphic encryption using ideal lattices
- Public-key cryptosystems from the worst-case shortest vector problem
- Efficient Fully Homomorphic Encryption from (Standard) LWE
- On lattices, learning with errors, random linear codes, and cryptography
- Trapdoors for hard lattices and new cryptographic constructions
- Title not available (Why is that?)
- (Leveled) fully homomorphic encryption without bootstrapping
- On lattices, learning with errors, random linear codes, and cryptography
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Bounds for Width Two Branching Programs
- Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller
- Pseudorandom Knapsacks and the Sample Complexity of LWE Search-to-Decision Reductions
- New lattice-based cryptographic constructions
- Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based
- Toward basing fully homomorphic encryption on worst-case hardness
Cited In (11)
- An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity
- Proofs of Proximity for Distribution Testing
- An Exponential Separation Between MA and AM Proofs of Proximity
- A characterization of constant‐sample testable properties
- Non-interactive proofs of proximity
- A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification
- Proofs of proximity for context-free languages and read-once branching programs
- Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs
- Title not available (Why is that?)
- Zero-Knowledge Proofs of Proximity
- A Hierarchy Theorem for Interactive Proofs of Proximity
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)
