Efficient constructions of hitting sets for systems of linear functions

DOI10.1007/BFB0023475zbMATH Open1499.68138MaRDI QIDQ5048940FDOQ5048940

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)

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

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)

Cites Work

• Hardness vs randomness
• Matchings and covers in hypergraphs
• On the power of two-point based sampling
• On the complexity of realization of partial Boolean functions by circuits of functional elements
• Approximating the Number of Zeroes of a GF[2] Polynomial
• Title not available (Why is that?)
• Title not available (Why is that?)
• Efficient construction of a small hitting set for combinatorial rectangles in high dimension
• Title not available (Why is that?)

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)