Efficient constructions of hitting sets for systems of linear functions

DOI10.1007/BFB0023475MaRDI QIDQ5048940zbMATH OpenFDO

Authors Alexander E. Andreev, Andrea Clementi, José Rolim

Publication date 9 November 2022

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Boolean functions (06E30) Networks and circuits as models of computation; circuit complexity (68Q06)

Recommendations

• Efficient construction of a small hitting set for combinatorial rectangles in high dimension
• scientific article; zbMATH DE number 1500656
• Optimal Hitting Sets for Combinatorial Shapes
• Optimal hitting sets for combinatorial shapes
• A lower bound for the hitting set size for combinatorial rectangles and an application

Cites work

• scientific article; zbMATH DE number 3980487 (Why is no real title available?)
• scientific article; zbMATH DE number 2102761 (Why is no real title available?)
• scientific article; zbMATH DE number 3405843 (Why is no real title available?)
• Approximating the Number of Zeroes of a GF[2] Polynomial
• Efficient construction of a small hitting set for combinatorial rectangles in high dimension
• Hardness vs randomness
• Matchings and covers in hypergraphs
• On the complexity of realization of partial Boolean functions by circuits of functional elements
• On the power of two-point based sampling

Cited in

(1)

• A nearly-optimal transfixing set

This page was built for publication: Efficient constructions of hitting sets for systems of linear functions

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