11 votes
Accepted

How do separations in of query complexities imply complexity class separations relative to oracles?

Let $\mathscr{F}$ be the collection of all functions $F:\{0,1\}^*\rightarrow\{0,1\}^*$, such that for every $n$, the restriction $F_n:=F|_{\{0,1\}^n}$ (restriction of $F$ on $\{0,1\}^n$) satisfies the ...
Wei Zhan's user avatar
  • 828
7 votes

Another planar separator ref question

Here is a proof using a well-known hammer. Let us assume wlog that $G$ is connected, hence it is a spanning tree plus $t+1$ edges. Clearly any cycle in $G$ must contain one of these $t+1$ edges ...
Chandra Chekuri's user avatar
1 vote

Can we efficiently distinguish between P and BPP?

You defined that algorithm $D$ distinguishes $BPP$ from $P$ if there exists a language $L \in BPP$ such that for all $A \in PTM$, $$D(\langle A\rangle) \in L \leftrightarrow D(\langle A \rangle) \...
Bjørn Kjos-Hanssen's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible