More Like this

1. On Uniform Convergence of Diagonal Multipoint Pad� Approximants For Entire Functions

   Lubinsky, Doron S (January 2019, Constructive approximation)

   We prove that for most entire functions f in the sense of category, a strong form of the Baker-Gammel-Wills Conjecture holds. More precisely, there is an inÖnite sequence S of positive integers n, such that given any r > 0, and multipoint PadÈ approximants Rn to f with interpolation points in fz : jzj  rg, fRngn2S converges locally uniformly to f in the plane. The sequence S does not depend on r, nor on the interpolation points. For entire functions with smooth rapidly decreasing coe¢ cients, full diagonal sequences of multipoint PadÈ approximants converge. 

   more » « less
2. Exact Interpolation, Spurious Poles, and Uniform Convergence of Multipoint Pade Approximants

   Lubinsky, Doron (July 2018, Sbornik : Mathematics)

   We prove that for most entire functions f in the sense of category, a strong form of the Baker-Gammel-Wills Conjecture holds. More precisely, there is an infinite sequence S of positive integers n, such that given any r>0, and multipoint Padé approximants R_{n} to f with interpolation points in {z:|z|≤r}, {R_{n}}_{n∈S} converges locally uniformly to f in the plane. The sequence S does not depend on r, nor on the interpolation points. For entire functions with smooth rapidly decreasing coefficients, full diagonal sequences of multipoint Padé approximants converge. 

   more » « less
3. On Super Strong ETH

   https://doi.org/10.1007/978-3-030-24258-9_28  

   Vyas, N.; Williams, R. (January 2019, Theory and Applications of Satisfiability Testing – SAT 2019)

   Multiple known algorithmic paradigms (backtracking, local search and the polynomial method) only yield a 2n(1−1/O(k)) time algorithm for k-SAT in the worst case. For this reason, it has been hypothesized that the worst-case k-SAT problem cannot be solved in 2n(1−f(k)/k) time for any unbounded function f. This hypothesis has been called the “Super-Strong ETH”, modeled after the ETH and the Strong ETH. We give two results on the Super-Strong ETH: 1. It has also been hypothesized that k-SAT is hard to solve for randomly chosen instances near the “critical threshold”, where the clause-to-variable ratio is 2^kln2−Θ(1). We give a randomized algorithm which refutes the Super-Strong ETH for the case of random k-SAT and planted k-SAT for any clause-to-variable ratio. For example, given any random k-SAT instance F with n variables and m clauses, our algorithm decides satisfiability for F in 2^n(1−Ω(logk)/k) time, with high probability (over the choice of the formula and the randomness of the algorithm). It turns out that a well-known algorithm from the literature on SAT algorithms does the job: the PPZ algorithm of Paturi, Pudlák and Zane [17]. 2. The Unique k-SAT problem is the special case where there is at most one satisfying assignment. Improving prior reductions, we show that the Super-Strong ETHs for Unique k-SAT and k-SAT are equivalent. More precisely, we show the time complexities of Unique k-SAT and k-SAT are very tightly correlated: if Unique k-SAT is in 2^n(1−f(k)/k) time for an unbounded f, then k-SAT is in 2^n(1−f(k)(1−ε)/k) time for every ε>0. 

   more » « less
4. On Super Strong ETH

   https://doi.org/10.1613/jair.1.11859  

   Vyas, Nikhil; Williams, Ryan (January 2021, Journal of Artificial Intelligence Research)

   Multiple known algorithmic paradigms (backtracking, local search and the polynomial method) only yield a 2n(1-1/O(k)) time algorithm for k-SAT in the worst case. For this reason, it has been hypothesized that the worst-case k-SAT problem cannot be solved in 2n(1-f(k)/k) time for any unbounded function f. This hypothesis has been called the "Super-Strong ETH", modelled after the ETH and the Strong ETH. It has also been hypothesized that k-SAT is hard to solve for randomly chosen instances near the "critical threshold", where the clause-to-variable ratio is such that randomly chosen instances are satisfiable with probability 1/2. We give a randomized algorithm which refutes the Super-Strong ETH for the case of random k-SAT and planted k-SAT for any clause-to-variable ratio. For example, given any random k-SAT instance F with n variables and m clauses, our algorithm decides satisfiability for F in  2n(1-c*log(k)/k) time with high probability (over the choice of the formula and the randomness of the algorithm). It turns out that a well-known algorithm from the literature on SAT algorithms does the job: the PPZ algorithm of Paturi, Pudlak, and Zane (1999).   The Unique k-SAT problem is the special case where there is at most one satisfying assignment. Improving prior reductions, we show that the Super-Strong ETHs for Unique k-SAT and k-SAT are equivalent. More precisely, we show the time complexities of Unique k-SAT and k-SAT are very tightly correlated: if Unique k-SAT is in  2n(1-f(k)/k) time for an unbounded f, then k-SAT is in 2n(1-f(k)/(2k)) time. 

   more » « less
5. Optimal Document Exchange and New Codes for Small Number of Insertions and Deletions

   Haeupler, Bernhard (October 2019, IEEE Symposium on Foundations of Computer Science)

   We give the first communication-optimal document exchange protocol. For any n and k 

   more » « less