Modeling polarization for Hyper-NA lithography tools and masks
Kafai Lai, Alan E. Rosenbluth, et al.
SPIE Advanced Lithography 2007
A function f:{0, 1}n → {0, 1} is called t-sparse if the n-variable polynomial representation of f over GF(2) contains at most t monomials. Such functions are uniquely determined by their values at the so-called critical set of all binary n-tuples of Hamming weight ≥n-[log2 t]-1. An algorithm is presented for interpolating any t-sparse function f, given the values of f at the critical set. The time complexity of the proposed algorithm is proportional to n, t, and the size of the critical set. Then, the more general problem of approximating t-sparse functions is considered, in which case the approximating function may differ from f at a fraction ε of the space {0, 1}n. It is shown that O((t/ε) · n) evaluation points are sufficient for the (deterministic) ε-approximation of any t-sparse function, and that an order of (t/ε)α(t,ε) · log n points are necessary for this purpose, where α(t, ε)≥0.694 for a large range of t and ε. Similar bounds hold for the t-term DNF case as well. Finally, a probabilistic polynomial-time algorithm is presented for the ε-approximation of any t-sparse function.
Kafai Lai, Alan E. Rosenbluth, et al.
SPIE Advanced Lithography 2007
Frank R. Libsch, S.C. Lien
IBM J. Res. Dev
Minkyong Kim, Zhen Liu, et al.
INFOCOM 2008
Arun Viswanathan, Nancy Feldman, et al.
IEEE Communications Magazine