Friday, November 21, 2003

Rational Functions and Decision-Tree Complexity

I thought I should mention some of my favorite and most frustrating open questions over the years. Here's one of them:

Let f:{0,1}n→{0,1}. Let h and g be n-variable degree d polynomials over the reals. Suppose for all x in {0,1}n, g(x)≠0 and f(x)=h(x)/g(x). Is there a constant k such that the decision-tree complexity of f is bounded by dk?

The decision-tree (or query) complexity is the number of bits of x that need to be viewed to determine f(x). The queries to the bits of x can be adaptive. I'm particularly interested in the case where d is poly-logarithmic in n.

Nisan and Szegedy answer the question in the affirmative if g(x)=1. Their result holds even if f(x) is only approximated by h(x). However if we allow arbitrary g(x), h(x)/g(x) can closely approximate the OR function which requires looking at all of the bits. The case where we require exact equality of f(x) and h(x)/g(x) is the open question at hand.

4 comments:

  1. Is there a reason we should consider rational functions (I meant is their an applicable model?)?

    ReplyDelete
  2. Is this related to your paper https://bibbase.org/network/publication/fortnow-worldstodieharderforopenoraclequestionsforthe21stcentury-2021?

    ReplyDelete
    Replies
    1. It's not directly connected to any of the questions in the survey, but it was motivated by a relativization question, namely does P = C=P \cap co=C=P relative to a generic oracle, though the combinatorial question is perhaps more interesting than its motivation.

      Delete
  3. The new paper that you mentioned on Mathstodon: https://arxiv.org/abs/2310.08004

    ReplyDelete