FPGA-based coprocessor for text string extraction
N.K. Ratha, A.K. Jain, et al.
Workshop CAMP 2000
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.
N.K. Ratha, A.K. Jain, et al.
Workshop CAMP 2000
David S. Kung
DAC 1998
Indranil R. Bardhan, Sugato Bagchi, et al.
JMIS
S. Sattanathan, N.C. Narendra, et al.
CONTEXT 2005