Sponsored by the Rutgers University Department of Mathematics and the

Center for Discrete Mathematics and Theoretical Computer Science (DIMACS)

**Co-organizers:****Andrew Baxter**, Rutgers University, baxter{at} math [dot] rutgers [dot] edu**Lara Pudwell**, Rutgers University, lpudwell {at} math [dot] rutgers [dot] edu**Doron Zeilberger**, Rutgers University, zeilberg {at} math [dot] rutgers [dot] edu

Title: Polynomial Approximation of Computationally-Hard Sequences

Speaker: **Aviezri Fraenkel**, Weizmann Institute, Israel

Joint Talk with Mathematics Colloquium

Date: Thursday, December 6, 2007 5:00pm

Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

The question whether an *m*-tuple (x_{1},...,x_{m}) in **Z**_{≥ 0}^{m} is in (a^{1},...,a^{m}), where the a^{i} are given integer sequences, can sometimes be decided *efficiently* (in polynomial time). More often, the answer is unknown, the best known algorithms being exponential. We present a polynomial approximate algorithm for deciding this question for some sequences a_{i}. Specifically, we consider the complementary sequences a_{n}=mex{a_{i}, b_{i} : 0 ≤ i < n}, b_{n} + |_ n/k _| (sequences A102528/9 in Sloane's encyclopedia for k=2). Using Fekete's Lemma we show that the polynomially computable sequences s_{n}=|_n α_|, t_{n}=|_n β_| where α = (√(17)+3)/4, β=α+1/2 are very good approximations, namely, s_{n-1} ≤ a_{n} ≤ s_{n}, t_{n-1} ≤ b_{n} ≤ t_{n} for all n ≥ 1 (k=2). We conjecture that the percentage of n for which a_{n}=s_{n}-1 is about 73%, a_{n}=s_{n}, 19%, a_{n}=s_{n}-2, 8%. Similar results for b_{n}, t_{n}. Analogous results for every fixed k>1. Existence of a limiting distribution, with one of the percentages dominant, would lead to first probabilistic algorithms for determining the winning positions of certain impartial games, where the (a^{1}, ..., a^{m}) are the second player winning positions.

Joint work with Udi Hadad.