Testers and their applications

DOI10.1145/2554797.2554828MaRDI QIDQ2988891zbMATH OpenOpenAlexFDO

Authors Nader H. Bshouty

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://doi.org/10.1145/2554797.2554828

zbMATH Keywords

\(d\)-restriction problemscombinatorial objectscover-free familiesderandomizationhitting setsperfect hashpolynomial identity testing (pit)polynomial restriction problemsseparating hash functionsuniversal sets

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Randomized algorithms (68W20)

Recommendations

• scientific article; zbMATH DE number 742944
• scientific article; zbMATH DE number 2086425
• Property testers for dense constraint satisfaction programs on finite domains
• Sub-Constant Error Low Degree Test of Almost-Linear Size
• Sub-constant error low degree test of almost-linear size

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

(16)

• Non-adaptive learning of a hidden hypergraph
• Lower bounds for matrix factorization
• On hitting-set generators for polynomials that vanish rarely
• Exact learning from an honest teacher that answers membership queries
• Non-adaptive learning of a hidden hypergraph
• Linear Time Constructions of Some d-Restriction Problems
• Fast algorithms for parameterized problems with relaxed disjointness constraints
• On the tensor rank of multiplication in finite extensions of finite fields and related issues in algebraic geometry
• Quantified Derandomization: How to Find Water in the Ocean
• Lower bounds for matrix factorization
• Almost optimal cover-free families
• scientific article; zbMATH DE number 7758310 (Why is no real title available?)
• Variety evasive subspace families
• Derandomizing multivariate polynomial factoring for low degree factors
• Adaptive exact learning of decision trees from membership queries
• Fooling near-maximal decision trees

This page was built for publication: Testers and their applications

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