🐱 Skyspace3.0

Search

SearchSearch

IQPs + friends

Feb 14, 202511 min read

current SotA

communication is measured in words ie sending 1 index is 1 communication cost (and bits)

modifications:

  • adaptive query prover (the default)
  • random sampling prover (evil prover can do whatever)

IQP (interactive query proof)

  • now we call comm and queries separate things
  • but we’ll always have them be the same

IQP(q,c) = queries, communication

MAQ (MA query):

  • the prover sends their claim for the entire string .

  • prover queries,
  • verifier queries
  • comms

Def CSIQP Exists , fast, such that always convinces you on yes instances but for any even moderately fast ,

“local reductions” — ykwim

Main results

prop1: If honest prover samples (a small number) of uniform random things and sends you a subset of of those, and you just look at those and nothing else, then such a protocol has an IQP because it’s basically just “count 1s”.

prop1.2: There exists a problem which is the following problem: write down indices . Put an easter egg at location in the YES instance, somewhere else in the NO instance.

claim: exists sampling csiqp verifier honest prover evil prover but not .

pf: if ver always accepts yes instances evil prover can modify string in very small number of locations to make it look like yes instance so ver prolly accepts the no instance too

prop2: a couple of things are equivalent to “HAS1” under local reductions.

prop3: problem: YES after first indices NO: before first indices

prop4: In (i.e., a tester) exists but not in

theorem5: for any const There exists a problem in

HOWEVER the pointer chasing problem is in the IQP-hierarchy and so is the XOR question.

you just split up the path and ask for checkpoints.

for XOR you chunk the thing

pf: pointer chasing

prop6: ckt evaluation is in the IQP hierarchy

q0: non promise problems: Any problem with a CSIQP also has an IQP.

q1: property testing also CSIQP ⇒ IQP

q2: Suppose you have a deterministic verifier, the honest prover samples non-adaptively but maybe with a weird pr distribution and then they can send you any indices not just the ones they queried.

suppose you had a CSIQP with such a prover and verifier. can this be turned into an IQP?

q3: is levin search thing legit?

q4: tester, IPP, but no dsIPP

q5: one prover wants you to say yes, one wants you to say no. they talk for some rounds and try to convince you.

question is, for example, is CSIQP contained in the IQP-hierarchy

some fun questions in the hierarchy: “every one is followed by a 2” or something

MAQ hierarchy — not interesting. IQP hierachy — very interesting IQP hierarchy = IQP with logn rounds of dudes talking

q6: Is a random problem in the IQP hierarchy?

q7: find something outside of the hierarchy

q8: if P=NP does the IQP hierarchy collapse?

q9: is all of IQP equiv to ckt evaluation

remark: If then this is contained in PH-IQP. Proof: say which one it is, then say if they’re lying

Thought: maybe we can make a “PRG” a language that’s not actually random but has enough properties to make it still not in the PH-IQP like we believe RAND to be.

Def of pseudorandom: Let be any subset of the hypercube obtained by restricting coordinates. We require that between many of the strings in are yes instances. and we require non promise problem, ie yes + no = all.

Claim this is not testable proof: yao, do some stuff ??? seems pretty believable

hope: maybe this is not anywhere in the IQP hierarchy!

OLD

update: we have changed the names of this thing because we’re mostly not thinking about property testing.

IQP (interactive query proof)

  • we care about reads = comms + queries
  • can do adaptive or random prover

MAQ (MA query):

  • the prover sends their claim for the entire string

CSIQP, dsIQP — just what you think they are.

  • Can still be interested in property testing ones
  • or non-promise ones
  • iyw

The “paths” example is quite good for the CSIPPs

a q from N — what else has a CSIPP

There are a couple of questions about IPPs that I think are pretty interesting.

Some context:

  • We mostly think about promise problems. That is,
    • there are some YES instances
    • some NO instances
    • and some banned instances
  • Property testing questions are quite interesting too. That is,
    • NO instances are things which are -far from every YES instance.

There are a couple of types of things that we think about:

  • testing
  • IPP
  • dsIPP
  • CSIPP

I’ll generally measure complexity by number of “reads” where “reads” = “communication + number of queries made to the string”.

Caution

I guess we’re measuring reads in “word RAM”. Like, if prover send verifier one index into the array, that counts as 1 read, and reading an index of the string counts as 1 read.

Be careful to not abuse this factor!

Talking about running time is also okay, but feels less standard.

You can ofc also separately track communication complexity and query complexity but this is kind of annoying.

Also, we sometimes care about verifier reads and prover reads.

questions

Q1: What are some questions that are not testable in time, but have IPPs?

Q2: What are some questions that don’t have IPPs (i.e., having a prover doesn’t improve over the complexity of just testing it yourself). For instance, questions where even with a prover, you still need to read approx the entire input.

OQ3: are there qs where strong provers can help, but weak provers cannot?
For instance, this could look like the following:

  • Test in queries.
  • IPP with Verifier making reads
  • But, if Prover makes reads, then the Verifier needs reads

(In other words, questions for which there is an IPP and a tester, but no dsIPP)

OQ4: are there qs where weak provers can help, but strong provers cannnot?\

  • Test in queries.
  • No IPP — no proof that helps verifier take time .
  • BUT, there is a CS-IPP (computationally secure).
  • That is, if you know that the Prover (even an evil Prover) has num queries bounded by , then there is some such good Prover that can help you beat queries.

I’ll assume that the bound on computation is the same on honest and malicious provers. It could be interesting to imagine that the malicious Prover is allowed a little extra juice.

Here’s a solution to OQ3 — although we’d like a “property testing” version of this:

  • valid instances: have exactly one
    • YES instances: occurs after the first the first spots
    • NO instance: occurs in the first spots

observe:

  • test in .
  • verify in read (remember we are in word RAM model)
  • but, if the Prover is efficient, the Verifier is stuck with doing reads.

Feb6 notes with N:

We tried to come up with examples for Q2 — promise problems without IPPs.

They mostly ended up looking like this:

  • YES instance = all zeroes
  • NO instance = at least one .

There are several problems that are hard due to being generalizations of this. For instance,

  • exact hamming weight
  • exact monotonicity for a boolean function on bits.

We came up with a notion of reduction for these problems. Basically, we’ll say problem A is harder than problem B if there’s a local transformation of inputs to problem that makes them into problems in A, with the same answer.

Something moderately surprising:

Suppose you have a set and want to distinguish between and .

It turns out that there’s a really easy round interactive protocol for this, where the communication is just sending element of each time (the verifier repeatedly asks for the -th largest element in , and the prover supposedly sends it back).

Some thoughts on OQ4:

@Nathan: How do we even define a “bounded adversary”?

Here’s a naive attempt, which is obviously bad:

with bounded such that for all , , and, bounded, , .

In case it’s not obvious, this is bad because can just hard-code some specific NO instance , and only has to trick on this one instance — but now knows the whole instance.

One way you could try to fix this is to just require that can’t trick you on most .

ok, so the req is:

We have a very weak version of the CS-IPP thing

problem:

  • distinguish between many ‘s
  • and less than many ‘s

A -bounded prover can generate a proof that requires 1 read to check. Whereas, for an unbounded prover, the verifier probably needs at least reads.

conjecture: strategy stealing can be done. (i.e., CSIPP is fake)

Let’s try to prove this for the case where

  • Bounded protocol with prover in reads, Verifier in read.

So we wanna generically show a decent protocol for unbounded provers ideally the Verifier should be reads.

  • Case 1: Honest prover is deterministic and non-adaptive

    • this is trivial.

  • Case 2: honest prover is randomized, but still non-adaptive.

ok, so the setup here is as follows:

  • if an honest Prover samples points, they’ll find a good thing to point at, and we’ll be convinced
  • for a random NO instance, it’s very unlikely that a random points has an element that you can point at which will convince the Verifier.

What this proves:

Suppose with being bounded and where is non-adaptive such that for all , , and, bounded, , .

Then, there exists an actual IPP for this problem too.
In fact, if you work in the “Random Oracle” model, you can make it a dsIPP

Proof: This really just does mean that YES instances have easter eggs and NO instances have at most easter eggs.

You can use the standard thing to prove bounds on sizes of sets.

Or, if you have a random oracle, you can ask the random oracle to specify a set of size , and then you are required to spit out an answer in that set. One really nice thing about this is that now we actually have only reads for the verifier (instead of above). The prover just has to say which index of the random oracles sized set the easter egg that it identified was.

todo: can we generalize this beyond 1 query things? can we get rid of the word “non-adaptive” ?

Interesting turn of events:

  • my above thing can easily be generalized to a dude that just samples some stuff and spits out a longer certificate

  • but the story for adaptive is different!

In particular consider the following problem:

You have a two pointer chains of length . One starts from the beginning of array, one starts from some random location.

In the YES instances, the chain starting from the beginning of the array ends in a smiley face, the other does not.

In the NO instance, the chain starting from the end of the array ends in a smiley face, the other does not.

If a bounded prover finds a smiley face and points to it, you can instantly be confident that it is a YES instacnce.

But, an unbounded prover can say nothing to convince a verifier unless the verifier is willing to just read the whole chain herself.

a couple of open qs: (more in picture)

  • can we find some other interesting problems with CSIQPs but no MAQs or whatever?

Graph View

Backlinks

  • No backlinks found