Non‐Abelian homomorphism testing, and distributions close to their self‐convolutions

DOI10.1002/rsa.20182zbMath1135.68065OpenAlexW217171368MaRDI QIDQ5436976

Don Coppersmith, Ronitt Rubinfeld, Michael Ben-Or, Mike Luby

Publication date: 18 January 2008

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20182

zbMATH Keywords

linearity testingsublinear time algorithmsconvolutions of distributions

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Specification and verification (program logics, model checking, etc.) (68Q60) Software, source code, etc. for problems pertaining to group theory (20-04)

Related Items (11)

Sampling Correctors ⋮ Property testing for cyclic groups and beyond ⋮ Stability of approximate group actions: uniform and probabilistic ⋮ On the distance between non-isomorphic groups. ⋮ Unnamed Item ⋮ On the local leakage resilience of linear secret sharing schemes ⋮ Unnamed Item ⋮ Testing properties of functions on finite groups ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Direct Sum Testing

Cites Work

• Linearity testing in characteristic two
• A PCP characterization of NP with optimal amortized query complexity
• Derandomizing homomorphism testing in general groups
• Randomness-efficient low degree tests and short PCPs via epsilon-biased sets
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

This page was built for publication: Non‐Abelian homomorphism testing, and distributions close to their self‐convolutions