Home

Daniel M. Kane

  1. On a Problem Relating to the ABC Conjecture.

    Fri, 04/15/2011 - 15:01 — SomNambul
    Authors: Daniel M. Kane
    Subjects: Number Theory
    Abstract

    We consider a variant of the ABC Conjecture, attempting to count the number
    of solutions to $A+B+C=0$, in relatively prime integers $A,B,C$ each of
    absolute value less than $N$ with $r(A)<|A|^a, r(B)<|B|^b, r(C)<|C|^c.$ The ABC
    Conjecture is equivalent to the statement that for $a+b+c<1$, the number of
    solutions is bounded independently of $N$. If $a+b+c \geq 1$, it is conjectured
    that the number of solutions is asymptotically $N^{a+b+c-1 \pm \epsilon}.$ We
    prove this conjecture as long as $a+b+c \geq 2.$

  2. Minimal S-universality criteria may vary in size.

    Tue, 02/01/2011 - 16:01 — SomNambul
    Authors: Scott D. Kominers, Daniel M. Kane, Noam D. Elkies
    Subjects: Number Theory
    Abstract

    In this note, we give simple examples of sets S of quadratic forms that have
    minimal S-universality criteria of multiple cardinalities. This answers a
    question of Kim, Kim, and Oh in the negative.

  3. $k$-Independent Gaussians Fool Polynomial Threshold Functions.

    Thu, 12/09/2010 - 16:01 — SomNambul
    Authors: Daniel M. Kane
    Subjects: Computational Complexity
    Abstract

    We show that any $O_d(\epsilon^{-4d 7^d})$-independent family of Gaussians
    $\epsilon$-fools any degree-$d$ polynomial threshold function.

  4. Unary Subset-Sum is in Logspace.

    Wed, 12/08/2010 - 16:02 — SomNambul
    Authors: Daniel M. Kane
    Subjects: Computational Complexity
    Abstract

    We present a Logspace algorithm that solves the Unary Subset-Sum problem.

  5. The Gaussian Surface Area and Noise Sensitivity of Degree-$d$ Polynomials.

    Tue, 12/15/2009 - 16:01 — SomNambul
    Authors: Daniel M. Kane
    Subjects: Computational Complexity
    Abstract

    We provide asymptotically sharp bounds for the Gaussian surface area and the
    Gaussian noise sensitivity of polynomial threshold functions. In particular we
    show that if $f$ is a degree-$d$ polynomial threshold function, then its
    Gaussian sensitivity at noise rate $\epsilon$ is less than some quantity
    asymptotic to $\frac{d\sqrt{2\epsilon}}{\pi}$ and the Gaussian surface area is
    at most $\frac{d}{\sqrt{2\pi}}$. Furthermore these bounds are asymptotically
    tight as $\epsilon\to 0$ and $f$ the threshold function of a product of $d$
    distinct homogeneous linear functions.

  6. Bounded Independence Fools Degree-2 Threshold Functions.

    Wed, 11/18/2009 - 16:01 — SomNambul
    Authors: Ilias Diakonikolas, Daniel M. Kane, Jelani Nelson
    Subjects: Computational Complexity
    Abstract

    Let x be a random vector coming from any k-wise independent distribution over
    {-1,1}^n. For an n-variate degree-2 polynomial p, we prove that E[sgn(p(x))] is
    determined up to an additive epsilon for k = poly(1/epsilon). This answers an
    open question of Diakonikolas et al. (FOCS 2009). Using standard constructions
    of k-wise independent distributions, we obtain a broad class of explicit
    generators that epsilon-fool the class of degree-2 threshold functions with
    seed length log(n)*poly(1/epsilon).

Math-arch

Syndicate content