skip to main content

Title: Hermite Rational Function Interpolation with Error Correction
We generalize Hermite interpolation with error correction, which is the methodology for multiplicity algebraic error correction codes, to Hermite interpolation of a rational function over a field K from function and function derivative values. We present an interpolation algorithm that can locate and correct <= E errors at distinct arguments y in K where at least one of the values or values of a derivative is incorrect. The upper bound E for the number of such y is input. Our algorithm sufficiently oversamples the rational function to guarantee a unique interpolant. We sample (f/g)^(j)(y[i]) for 0 <= j <= L[i], 1 <= i <= n, y[i] distinct, where (f/g)^(j) is the j-th derivative of the rational function f/g, f, g in K[x], GCD(f,g)=1, g <= 0, and where N = (L[1]+1)+...+(L[n]+1) >= C + D + 1 + 2(L[1]+1) + ... + 2(L[E]+1) where C is an upper bound for deg(f) and D an upper bound for deg(g), which are input to our algorithm. The arguments y[i] can be poles, which is truly or falsely indicated by a function value infinity with the corresponding L[i]=0. Our results remain valid for fields K of characteristic >= 1 + max L[i]. Our algorithm more » has the same asymptotic arithmetic complexity as that for classical Hermite interpolation, namely soft-O(N). For polynomials, that is, g=1, and a uniform derivative profile L[1] = ... = L[n], our algorithm specializes to the univariate multiplicity code decoder that is based on the 1986 Welch-Berlekamp algorithm. « less
; ;
Award ID(s):
Publication Date:
Journal Name:
Proc. Computer Algebra in Scientific Computing (CASC) 2020
Sponsoring Org:
National Science Foundation
More Like this
  1. Amir Hashemi (Ed.)
    We present Hermite polynomial interpolation algorithms that for a sparse univariate polynomial f with coefficients from a field compute the polynomial from fewer points than the classical algorithms. If the interpolating polynomial f has t terms, our algorithms, require argument/value triples (w^i, f(w^i), f'(w^i)) for i=0,...,t + ceiling( (t+1)/2 ) - 1, where w is randomly sampled and the probability of a correct output is determined from a degree bound for f. With f' we denote the derivative of f. Our algorithms generalize to multivariate polynomials, higher derivatives and sparsity with respect to Chebyshev polynomial bases. We have algorithms that can correct errors in the points by oversampling at a limited number of good values. If an upper bound B >= t for the number of terms is given, our algorithms use a randomly selected w and, with high probability, ceiling( t/2 ) + B triples, but then never return an incorrect output. The algorithms are based on Prony's sparse interpolation algorithm. While Prony's algorithm and its variants use fewer values, namely, 2t+1 and t+B values f(w^i), respectively, they need more arguments w^i. The situation mirrors that in algebraic error correcting codes, where the Reed-Solomon code requires fewer values thanmore »the multiplicity code, which is based on Hermite interpolation, but the Reed-Solomon code requires more distinct arguments. Our sparse Hermite interpolation algorithms can interpolate polynomials over finite fields and over the complex numbers, and from floating point data. Our Prony-based approach does not encounter the Birkhoff phenomenon of Hermite interpolation, when a gap in the derivative values causes multiple interpolants. We can interpolate from t+1 values of f and 2t-1 values of f'.« less
  2. Multiplicity code decoders are based on Hermite polynomial interpolation with error correction. In order to have a unique Hermite interpolant one assumes that the field of scalars has characteristic 0 or >= k+1, where k is the maximum order of the derivatives in the list of values of the polynomial and its derivatives which are interpolated. For scalar fields of characteristic k+1, the minimum number of values for interpolating a polynomial of degree <= D is D+1+2E(k+1) when <= E of the values are erroneous. Here we give an error-correcting Hermite interpolation algorithm that can tolerate more errors, assuming that the characteristic of the scalar field is either 0 or >= D+1. Our algorithm requires (k+1)D + 1 - (k+1)k/2 + 2E values. As an example, we consider k = 2. If the error ratio (number of errors)/(number of evaluations) <= 0.16, our new algorithm requires ceiling( (4+7/17) D - (1+8 /17) ) values, while multiplicity decoding requires 25D+25 values. If the error ratio is <= 0.2, our algorithm requires 5D-2 evaluations over characteristic 0 or >= D+1, while multiplicity decoding for an error ratio 0.2 over fields of characteristic 3 is not possible for D >= 3. Our algorithmmore »is based on Reed-Solomon interpolation without multiplicities, which becomes possible for Hermite interpolation because of the high redundancy necessary for error-correction.« less
  3. Abstract

    We continue the program of proving circuit lower bounds via circuit satisfiability algorithms. So far, this program has yielded several concrete results, proving that functions in$\mathsf {Quasi}\text {-}\mathsf {NP} = \mathsf {NTIME}[n^{(\log n)^{O(1)}}]$Quasi-NP=NTIME[n(logn)O(1)]and other complexity classes do not have small circuits (in the worst case and/or on average) from various circuit classes$\mathcal { C}$C, by showing that$\mathcal { C}$Cadmits non-trivial satisfiability and/or#SAT algorithms which beat exhaustive search by a minor amount. In this paper, we present a new strong lower bound consequence of having a non-trivial#SAT algorithm for a circuit class${\mathcal C}$C. Say that a symmetric Boolean functionf(x1,…,xn) issparseif it outputs 1 onO(1) values of${\sum }_{i} x_{i}$ixi. We show that for every sparsef, and for all “typical”$\mathcal { C}$C, faster#SAT algorithms for$\mathcal { C}$Ccircuits imply lower bounds against the circuit class$f \circ \mathcal { C}$fC, which may bestrongerthan$\mathcal { C}$Citself. In particular:

    #SAT algorithms fornk-size$\mathcal { C}$C-circuits running in 2n/nktime (for allk) implyNEXPdoes not have$(f \circ \mathcal { C})$(fC)-circuits of polynomial size.

    #SAT algorithms for$2^{n^{{\varepsilon }}}$2nε-size$\mathcal { C}$C-circuits running in$2^{n-n^{{\varepsilon }}}$2nnεtime (for someε> 0) implyQuasi-NPdoes not have$(f \circ \mathcal { C})$(fC)-circuits of polynomial size.

    Applying#SAT algorithms from the literature, one immediate corollary of our results is thatQuasi-NPdoes not haveEMAJACC0THRcircuits of polynomialmore »size, whereEMAJis the “exact majority” function, improving previous lower bounds againstACC0[Williams JACM’14] andACC0THR[Williams STOC’14], [Murray-Williams STOC’18]. This is the first nontrivial lower bound against such a circuit class.

    « less
  4. A gr e at d e al of i nt er e st s urr o u n d s t h e u s e of tr a n s cr a ni al dir e ct c urr e nt sti m ul ati o n (t D C S) t o a u g m e nt c o g niti v e tr ai ni n g. H o w e v er, eff e ct s ar e i n c o n si st e nt a cr o s s st u di e s, a n d m et aa n al yti c e vi d e n c e i s mi x e d, e s p e ci all y f o r h e alt h y, y o u n g a d ult s. O n e m aj or s o ur c e of t hi s i n c o n si st e n c y i s i n di vi d u al diff er e n c e s a m o n g t h e pmore »arti ci p a nt s, b ut t h e s e diff er e n c e s ar e r ar el y e x a mi n e d i n t h e c o nt e xt of c o m bi n e d tr ai ni n g/ sti m ul ati o n st u di e s. I n a d diti o n, it i s u n cl e ar h o w l o n g t h e eff e ct s of sti m ul ati o n l a st, e v e n i n s u c c e s sf ul i nt er v e nti o n s. S o m e st u di e s m a k e u s e of f oll o w- u p a s s e s s m e nt s, b ut v er y f e w h a v e m e a s ur e d p erf or m a n c e m or e t h a n a f e w m o nt hs aft er a n i nt er v e nti o n. H er e, w e utili z e d d at a fr o m a pr e vi o u s st u d y of t D C S a n d c o g niti v e tr ai ni n g [ A u, J., K at z, B., B u s c h k u e hl, M., B u n arj o, K., S e n g er, T., Z a b el, C., et al. E n h a n ci n g w or ki n g m e m or y tr ai ni n g wit h tr a n scr a ni al dir e ct c urr e nt sti m ul ati o n. J o u r n al of C o g niti v e N e u r os ci e n c e, 2 8, 1 4 1 9 – 1 4 3 2, 2 0 1 6] i n w hi c h p arti ci p a nts tr ai n e d o n a w or ki n g m e m or y t as k o v er 7 d a y s w hil e r e c ei vi n g a cti v e or s h a m t D C S. A n e w, l o n g er-t er m f oll o w- u p t o a ss es s l at er p erf or m a n c e w a s c o n d u ct e d, a n d a d diti o n al p arti ci p a nt s w er e a d d e d s o t h at t h e s h a m c o n diti o n w a s b ett er p o w er e d. W e a s s e s s e d b a s eli n e c o g niti v e a bilit y, g e n d er, tr ai ni n g sit e, a n d m oti v ati o n l e v el a n d f o u n d si g nifi c a nt i nt er a cti o ns b et w e e n b ot h b as eli n e a bilit y a n d m oti v ati o n wit h c o n diti o n ( a cti v e or s h a m) i n m o d els pr e di cti n g tr ai ni n g g ai n. I n a d diti o n, t h e i m pr o v e m e nt s i n t h e a cti v e c o nditi o n v er s u s s h a m c o n diti o n a p p e ar t o b e st a bl e e v e n a s l o n g a s a y e ar aft er t h e ori gi n al i nt er v e nti o n. ■« less
  5. F or c e d at a f or a fl a p pi n g f oil e n er g y h ar v e st er wit h a cti v e l e a di n g e d g e m oti o n o p er ati n g i n t h e l o w r e d u c e d fr e q u e n c y r a n g e i s c oll e ct e d t o d et er mi n e h o w l e a di n g e d g e m oti o n aff e ct s e n er g y h ar v e sti n g p erf or m a n c e. T h e f oil pi v ot s a b o ut t h e mi dc h or d a n d o p er at e s i n t h e l o w r e d u c e d fr e q u e n c y r a n g e of 𝑓𝑓more »𝑓𝑓 / 𝑈𝑈 ∞ = 0. 0 6 , 0. 0 8, a n d 0. 1 0 wit h 𝑅𝑅 𝑅𝑅 = 2 0 ,0 0 0 − 3 0 ,0 0 0 , wit h a pit c hi n g a m plit u d e of 𝜃𝜃 0 = 7 0 ∘ , a n d a h e a vi n g a m plit u d e of ℎ 0 = 0. 5 𝑓𝑓 . It i s f o u n d t h at l e a di n g e d g e m oti o n s t h at r e d u c e t h e eff e cti v e a n gl e of att a c k e arl y t h e str o k e w or k t o b ot h i n cr e a s e t h e lift f or c e s a s w ell a s s hift t h e p e a k lift f or c e l at er i n t h e fl a p pi n g str o k e. L e a di n g e d g e m oti o n s i n w hi c h t h e eff e cti v e a n gl e of att a c k i s i n cr e a s e d e arl y i n t h e str o k e s h o w d e cr e a s e d p erf or m a n c e. I n a d diti o n a di s cr et e v ort e x m o d el wit h v ort e x s h e d di n g at t h e l e a di n g e d g e i s i m pl e m e nt f or t h e m oti o n s st u di e d; it i s f o u n d t h at t h e m e c h a ni s m f or s h e d di n g at t h e l e a di n g e d g e i s n ot a d e q u at e f or t hi s p ar a m et er r a n g e a n d t h e m o d el c o n si st e ntl y o v er pr e di ct s t h e a er o d y n a mi c f or c e s.« less