Shuichi Hirahara The University of Tokyo
CCC 18/6/2015
Dishonest oracle Selector Our Contributions 1. We formulate the notion of selector. ♪ ﾖSelector ⇒ Able to remove short advice 2. We prove the existence of a selector for EXPNP_ complete languages.
• Introduced by Blum & Kannan (1989). • An instance checker for a function f checks if a given oracle correctly computes f ( x ) on input x in polynomial time. Possibly buggy program (modeled by black-box access to an oracle)
✓There exist instance checkers for P#P-, PSPACE-, [LFKN92, Sha92, BFL91] EXP-complete languages. ✔Any languages with an instance checker must be in NEXP ∩ coNEXP.  (Note: NEXP ⊆ EXPNP) Possibly buggy program (modeled by black-box access to an oracle)
Given: 1. An input φ, and 2. access to two oracles one of which is honest. Task: compute SAT(φ) with the help of the oracles Given: input φ
Given: 1. An input φ, and 2. access to two oracles one of which is honest. Task: compute SAT(φ) with the help of the oracles
one of which is honest. with the help of the oracles
Given: 1. An input φ, and 2. access to two oracles one of which is honest. Task: compute SAT(φ) with the help of the oracles
Given: 1. An input φ, and 2. access to two oracles one of which is honest. Task: compute SAT(φ) with the help of the oracles
2. access to two oracles one of which is honest. Essential Task: determine which is honest when they disagree on φ .
Definition (Selector) A selector S for a language L is a polynomial-time probabilistic oracle machine such that Ao = L or A1 = L  ⇒  Pr[SAo,A1(x) = L(x)] ≥ 0.99 (for any A 0 , A 1 드{0,1}*, x  ∈ {0,1}*) (polynomial-time probabilistic oracle TM)
Definition (Deterministic Selector) A deterministic selector S for a language L is a polynomial- time deterministic oracle machine such that Ao = L or A1 = L = SAo,A1(x) = L(x) (for any A 0 , A 1  ⊆ {0,1}*, x  ∈ {0,1}*) (polynomial-time deterministic oracle TM)
[Krentel 1988] Def. (Lexicographically Maximum Satisfying Assignment) Input: a Boolean formula φ: {0, 1} n → {0, 1} and an index k Output: the kth bit of the lexicographically maximum satisfying assignment of φ . Goal: to construct a deterministic selector for this language. Given: an input (φ, k) and two oracles   ξ
Show us the 1st bit of the satisfying assignment! • Make queries (φ, 1), ..., (φ, n) to the oracles: The lexicographically maximum satisfying assignment of φ is... • If v 0 = v 1 , then output the k th bit of v 0 (= v 1 ). • Else, we have ν 0 ≠ ν 1 .  We assume ν 0 < ν 1 . Evaluate φ(ν 1 ). • We trust B if φ(ν 1 ) = 1 and trust  B otherwise. (i.e. output the k th bit of ν o ) (i.e. output the k th bit of v 1 ) ) F.D.
Theorem (Main Result) There exists a selector for EXPNP-complete languages. Proof sketch: Def. (An EXPNP -complete language) Input: a succinctly described Boolean formula Φ: {0, 1}²"  → {0, 1} and an index k Output: the kth bit of the lexicographically maximum satisfying assignment of Φ.
▷ Proof strategy: the same with PNP-complete languages We are given a (succinctly described) exponential- sized formula Φ and two oracles  空港1 E {0,1}2n Step 1: Which is the larger? (i.e. compute Vo < V1) ✓  Binary search & Polynomial identity testing Step 2: Is V 1 a satisfying assignment of Φ? ✓  Can be done in the same way with MIP = NEXP. [Babai, Fortnow, Lund (1991)].
✔ The task of selectors is strictly easier than instance checking.
[Karp & Lipton (1980)] SAT ∈ P/log ⇒ SAT ∈ P [Trevisan & Vadhan (2002)] EXP ⊆ BPP/log ⇒ EXP ⊆ BPP ✓ This follows from the instance checkability of EXP-complete languages. When can we remove short advice? A. When we have a selector.
1. Suppose L is computable with 1-bit advice.
M computes L correctly. 0) = L(q) or M(q, 1) = L(q) for any q ∈ {0,1} ( as follows: (We assume that L is paddable and q's are of the same length.) One of these oracles is honest! ⇒The selector can compute L correctly (without any advice).
Identifying an honest oracle among two Identifying an honest oracle among polynomially many Able to remove advice of 1 bit > Able to remove advice of O (log n ) bits
➤ The notion of selector provides a general framework to remove short advice: Thm. (⇒ Selector ⇒ Able to remove short advice) For any paddable language L, the following are equivalent: 1. There exists a deterministic selector for L. L ∈ P/log  implies L ∈ P under any relativized world. 2. In other words, L E PR/log ⇒ L E PR    (∀R: oracle) ✔ The converse direction (2 ⇒ 1) also holds in this sense!
▷ The notion of selector provides a general framework to remove short advice: Thm. (⇒ Selector ⇒ Able to remove short advice) For any paddable language L, the following are equivalent: There exists a probabilistic selector for L. 1. L ∈ BPP/log  implies L ∈ BPP under any relativized world. In other words, L ∈ BPPR /log ⇒ L ∈ BPPR    (VR: oracle) Technical Remark: This works for any type of advice for BPP, because we can remove the most powerful advice (i.e.BPP//log).
Identifying an honest oracle among two Identifying an honest oracle among polynomially many Able to remove advice of 1 bit > Able to remove advice of O (log n ) bits
• We have a selector (Honest) oracle among two. • Given input x and many oracles • Ask them about x: L(x) is • Divide them into two teams: Idea: “Tournament”
✓The honest oracle always wins!
• Pick arbitrary two oracles
• Run the selector outputs 0, then we doubt • If (the oracle loses!); otherwise we doubt •  Continue it until one of the teams wins and trust the team. Q.E.D.
Corollary (Selector ⇒ Removing short advice) Suppose that there exists a selector for a paddable language L. Then, L ∈ P/log implies L ∈ P (under any relativized world).
Claim (∃ Selector ⇐ Able to remove short advice) Suppose L ∈ P/log  implies L ∈ P under any relativized world. Then, there exists a deterministic selector for L. → We prove the contraposition: If no selector exists, then for some relativized world, even 1-bit advice cannot be removed: ∃R s.t.  L ∈ PR/1  &  L ∈ PR ▷ Constructing such an oracle R by diagonalization. ▷  1-bit advice can tell which is honest. (i.e. L E PR/1)

Theorem (Deterministic Selector)
1. There exists a deterministic selector for PSPACE-complete languages. Any languages with a deterministic selector sit within PSPACE. 2. Deterministic selectors are in PSPACE 3 deterministic selector
Theorem (Upper Bound for Probabilistic Selector) Any languages with a selector sit within Sexp S
✓The existence of a selector ⇒ A property of removing short advice under any relativized world. ✔There exists a selector for EXPNP-complete languages. ▷We can efficiently identify an honest EXPNP-complete oracle among many.
• Closing the gap between EXPNP and Sexp ▷Does there exist a selector for promise-Sexp -complete languages? • Does there exist a selector for NEXP-complete languages? ▷Although NEXP ⊆ EXPNP, the set of languages with a selector is not closed under downward reduction. • What about removing advice of polynomial size? ▷e.g. { L | ∀R,  L ∈ P R /poly ⇒ L ∈ MA R } % 10n ;