Algorithmic construction of sets for k-restrictions

By Noga Alon, Dana Moshkovitz, Shmuel Safra. TALG, 2006

314 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Towards Fast Computation of Certified Robustness for ReLU Networks (2018, methodology): “Theorem A.6 ((Raz & Safra, 1997; Alon et al., 2006; Dinur & Steurer, 2014)).”
Optimizing password composition policies (2013, background): “It is a known fact that there exist Set-Cover instances, with (g, m, t) all polynomially dependent of each other, that are hard to approximate to a factor of c ln n [Alon et al. 2006].”
Minimal Controllability Problems (2013, methodology): “index k2 ∈{1,...,m+p+1}in the support of the i2’nd row of Vb and we set set 2Intractabilityresultsforminimalcontrollabilityproblems 9 b k1 and b k2 to be, say, independent uniform random variables on [1,2]. Finally, we add r to Sby setting b r to a positive continuous random variable, to to make sur”
Wireless Charging Technologies: Fundamentals, Standards, and Network Applications (2015, unknown): “The simulation showed that the heuristic approach reaches a close-to-optimal performance and largely outperforms a setcover-based approach [311], that maximizes the number of under-charged devices nearby each stop.”