Parameterized testability

DOI10.1145/2554797.2554843zbMATH Open1364.68363OpenAlexW2296151834MaRDI QIDQ2988904FDOQ2988904

Authors: Yuichi Yoshida, Kazuo Iwama 

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.2554843

Recommendations

• Parameterized testability
• Parameterized study of the test cover problem
• Parameter testing in bounded degree graphs of subexponential growth
• Property testing and its connection to learning and approximation
• Parameterizations of test cover with bounded test sizes

zbMATH Keywords

property testingfixed parameter tractability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

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 (3)

• Parameterized testability
• Parameterized property testing of functions
• Title not available (Why is that?)

This page was built for publication: Parameterized testability

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