One of the neatest areas of town is the Avenue of Fashion. If you don't know about it, you should. It has a ton of history. We just did a big list over here.
If you head down Livernois between 7 and 8 mile, you're going to find what is shaping up to be a stylish new entrant into the coffee game over there. That's the Narrow Way Cafe & Shop, tucked next to Kuzzo's Chicken and Waffles.
It's a partnership of the Merritt family. That's a last name some Detroiters would know as the dad is Bishop Andrew Merritt of Straight Gate Church, or for Merit Goodness, a clothing brand where the proceeds go to youth development that is a project of David Merritt.
I caught up with Jonathan Merritt outside the shop, which is a family business co-owned by the Bishop and the brothers.
Part of the project is some help from Zingerman's Coffee and Bakehouse in Ann Arbor. It's a special collaboration in that it's more than just selling their goods, but also mentorship.
"We're going to be selling is baked goods, coffee, any kind of coffee, espresso drinks, specialties, special drinks, smoothies. We have some amazing smoothies in our line-up. One with the baked pastries, little small menu of food but we are very, very excited about the opportunity to open up within the next weeks," said Merritt.
Checking out the interior in progress, this looks like one of those places that will have quality stuff and the interior looks to go with it.
One nice touch of the space is the garage door-style entrance that opens the establishment out into the street.
The project is a Motor City Match winner, receiving $45,000. Originally planned to open in April, they're now on track to open in a few weeks.


Looking for a new adventure? Join the IDS family!
IDS provides laboratories worldwide with clinical and research solutions in the field of specialty endocrinology. We aim to enhance laboratory efficiency, improve diagnostic accuracy and enrich diagnostic outcomes for patients.
We develop, manufacture and market innovative immunoassays and automated immunoanalyser technologies to provide improved diagnostic outcomes for patients. Our immunoassay portfolio is a combination of an endocrinology specialty testing menu and assay panels in complementary fields.
Immunodiagnostic Systems Holdings PLC (hereafter referred to as IDS) is a leading in-vitro diagnostic solution provider to the clinical laboratory market. IDS was founded in 1977 and trades on the Alternative Investment Market (AIM; trading symbol IDH) of the London Stock Exchange. We are a global company headquartered in the UK with around 275 employees worldwide. Our products are developed and manufactured at our facilities in Europe. We serve our customers through regional offices in Europe and the USA, and have sales offices in Brazil. Our network of distributors works on our behalf to serve our customers throughout the rest of the world.
Our Global Headquarters are in the UK – and we have direct sales offices in Brazil, France, Germany and the USA. Our key manufacturing sites are based in Belgium, France, Italy and the UK. Our network of distributors support us in reaching clients worldwide with our innovative specialty immunoassay solutions.
View contact details for your area, by selecting from the drop-down menu, or clicking on the map.


Systemic lupus erythematosus continues to intrigue clinicians and investigators as a model of autoimmunity. The multisystem nature of this entity, the plethora of immunologic and self-reactive abnormalities, and the availability of animal models make lupus an ideal model for study. In addition, the clinical consequences of the exaggerated immune responses continue to challenge clinicians who care for patients with lupus.
Published: Ann Intern Med. 1987;107(1):130-131.


I had a discussion with a colleague recently when he made a statement regarding salesperson types, specifically hunters versus farmers. His perception was that you are either one or the other and that hunters are a much rarer breed.
The reality is that certain people may be predisposed to be more effective in a hunter role but that is supported by their core skill set and the learned behaviours they have developed over time. That does not mean that skills cannot be acquired or effectively building repeatable processes and doing the right things will not allow others to be successful within a hunter role.
Great article that provides the details without the associated hype. I maybe biase as I am a big fan of their technology and many of my clients use it as well.
It provides a solid platform to store millions of tiny files such as email effectively and securely. Many players in the market make this claim but try retrieving the information as the data store grows and you will understand why I am a big fan.
Data resides in your current system that is on legal hold as well as other data maintained from a compliance perspective. Static or fixed period legal holds will need to be addressed very differently from dynamic ongoing holds that represent historical and future data. While you maintain the data in GroupWise, Office 365, personal archives, tape or all of them. This is something that does need to considered as part of the migration decision.
If you allow personal archives it has been shown in many recent cases that you are in breach of your own policy even if you leave the option to archive up to the users. If instruction is provided to users on how to address older dates, then that weakens your position and a well-versed lawyer will definitely take advantage of the opportunity to have all personal archives and backups easily included as part of a discovery request.
I have to first say bravo to U.S. District Judge Richard Posner for his intelligent stand in the patent arena. All the recent information floating around in the media, publications and web based content regarding patents would make it seem that we have a scarcity of innovation. The trivial nature of some of these patents seem more focused on hoarding what success they may have attained or extending the basking period if possible.
The patent related litigations have increased greatly over the years and according to the research available, the number of cases commenced has more that quadrupled between 1980 and 2010. The situation is getting out of control and in my opinion the only people truly benefiting are the patent related legal folks. I maybe generalizing as there is a definite need for copyrights and patents when applied to the right things and for the right reason as intended.
Market: Experience has shown that most migrations take one of three paths to address personal archives as part of a migration. It is very rare that at the end of a migration that some disposition is not taken to account for legacy data. I have had some great clients who had started with a "no personal archive migration" position but eventually came around due to business unit intervention or certain executives or senior folks within the organization driving the need to have access to this data.


Mar 17, 2017 . Grinding circuits are made up of large, moving pieces of machinery. When carrying or moving objects in and around this equipment extreme care should be taken. As an example, when operating the crane, never hoist anything directly over the mills. If it is necessary to take long pieces of material, like pipes.
GAR BRO Manufacturing Co Equipment engineering services specializing in concrete placing, concrete buckets, concrete skip pans, industrial buckets, cable buckets, cable hooks, concrete hoppers, receiving hoppers, floor hoppers and custom equipment.
Dec 16, 2016 . MSE Supplies is excited to announce the new compact ball mills that fit in a glove box, and the jar mill designs with OSHA safety compliance. Right now, your l.
Dec 5, 2014 . Here's a list of the most important safety maintenance steps that all operators should follow when using a ball mill.
Source: YouTube. Added: 10 years ago. Tags: ball, mill, safety, equipment. Categories: Library. Description: Mine Safety and Health Administration Ball Mill Safety DVD573 1998 Developed cooperatively by MSHA and Lehigh Portland Cement Company. Outlines the various steps precautions and procedures that must.
Transmin's nickel processing customer eliminates all safety risks with their A Ward ball mill ball container unloaders. . Steel Balls. Equipment: 20ft slightly customized Flat Deck container unloaders . A ball mill is a type of grinder that is used to grind and downsize mined materials such as copper, gold, iron ore and nickel.
The extremely high centrifugal forces of a planetary ball mill result in very high pulverization energy and therefore short grinding times. . contamination free grinding; Safety Slider for safe operation; perfect stability on lab bench thanks to FFCS technology; innovative counter weight and imbalance sensor for unsupervised.
environmental protection and other research and industry sector. Product Features: 1. With small size, light weight, low noise. 2 can be operated continuously, one way running, automatic positive and reverse continuous and regular operation. 3 series of ball mill can be dry grinding, wet grinding, vacuum grinding, protection.
Dec 26, 2017 . Borner Powerline Wave Waffle Cutter with Adjustable Safety. This great kitchen tool makes it easier than . safety ppt on cement ball mill maintenance bmcindia.in. Mill Lubrication System .. Channel who hosts Dirty Jobs? A viewer recently called him out on not wearing the proper safety gear on his show.
safety equipment mining sa Grinding Mill China. Mining Safety Equipment Suppliers in South Africa . SupplyMine. Find Mining Safety Equipment Suppliers in South Africa. Search over 16000 suppliers covering the. Get More Info. image.
Free Essays on Industrial Safety Eassy through Essay Depot. Free Essays on Industrial Safety Eassy. . Ore dressing equipments mainly include cement mill,ball . Industrial Safety Management. Essay On Liberalization And . Chat Online.


text:
Q: Show DIV On Highlight Then Hide I'm attempting to have a hidden div tag display when highlighting specific text.  I was able to get a hidden div to display on highlighting but the 2 parts I cannot accomplish are:

*

*Only show when highlighting specific text (I assume using a span tag id or something similar)

*After the display has been changed to block, change it back to hidden after 5 seconds.
Here is my attempt.  Again, this does show the hidden div on highlighting but that's as far as I got.  Please help!

 function ShowNote() {
   document.getElementById('Note').style.display = 'block';
 }

 document.onmouseup = ShowNote;
 if (!document.all) document.captureEvents(Event.MOUSEUP);

 function HideNote() {
   document.getElementById('Note').style.display = 'hidden';
 }
 setTimeout("HideNote()", 5000); // after 5 secs
I DON'T want it to show when I highlight this text

I DO want it to show when I highlight this text.

HIDDEN DIV CONTENT

A: You're very close!
Here's what I have:

function ShowNote() {
    if(window.getSelection() == "I DO want it to show when I highlight this text.")
        document.getElementById('Note').style.display = 'block';
        setTimeout(function(){
         document.getElementById('Note').style.display = 'none';
        }, 5000); // after 5 secs
    }

    document.onmouseup = ShowNote;
    if (!document.all) document.captureEvents(Event.MOUSEUP);
I DON'T want it to show when I highlight this text

    I DO want it to show when I highlight this text.

HIDDEN DIV CONTENT

Changes:

*

*You need to check what is highlighted via the "window.getSelection()"
function.

*You were passing a string to setTimeout

*hidden isn't a valid display option, none is

So you know, it's generally bad practice to just have text floating around outside of tags. So it's best to stick your first two lines in
 tags or something.

A: You are using quite old and antiquated code. Here's the modern approach:

function showNote() {
   document.getElementById('Note').classList.remove("hide");
   setTimeout(hideNote, 5000); // after 5 secs
}

function hideNote(){
  document.getElementById("Note").classList.add("hide");
}

document.getElementById("select").addEventListener("mouseup", showNote);
.hide { display: none; }

#select { color:red; }

I DON'T want it to show when I highlight this text

I DO want it to show when I highlight this text.

HIDDEN DIV CONTENT

A: This is what I did for you.
I setup interval. that occurs every time you mouse out.Or even better it will check if it's your div's style is block on the page.
Hope this helps
Live exapmle on Codepen
var target = document.getElementById('note');

var i = setInterval(function(){
   if (document.getElementById("note").style.display == 'block') {
    hide();
  }
}, 5000);

function showNote() {
  target.style.display = 'block';
}
function hide(){
 document.getElementById("note").style.display = "none";
}

redpajama_set_name: RedPajamaStackExchange


text:
package com.github.nrudenko.dora.compiler;

import com.github.nrudenko.dora.annotation.DbColumn;
import com.github.nrudenko.dora.annotation.DbSkipField;
import com.github.nrudenko.dora.annotation.Table;
import com.github.nrudenko.dora.compiler.exception.BaseCompilerException;
import com.github.nrudenko.dora.compiler.model.TableModel;
import com.github.nrudenko.dora.compiler.template.BaseTemplateContext;
import com.github.nrudenko.dora.compiler.template.ConverterContext;
import com.github.nrudenko.dora.compiler.template.SchemeContext;
import com.google.auto.service.AutoService;

import javax.annotation.processing.AbstractProcessor;
import javax.annotation.processing.Processor;
import javax.annotation.processing.RoundEnvironment;
import javax.lang.model.SourceVersion;
import javax.lang.model.element.Element;
import javax.lang.model.element.ElementKind;
import javax.lang.model.element.TypeElement;
import javax.tools.Diagnostic;
import javax.tools.JavaFileObject;
import java.io.BufferedWriter;
import java.io.IOException;
import java.util.HashSet;
import java.util.Set;

@AutoService(Processor.class)
public class TableProcessor extends AbstractProcessor {

    @Override
    public boolean process(Set<? extends TypeElement> annotations, RoundEnvironment roundEnv) {
        Set<? extends Element> tableElements = roundEnv.getElementsAnnotatedWith(Table.class);
        for (Element element : tableElements) {
            if (element.getKind() == ElementKind.CLASS) {
                try {
                    processTable(element);
                } catch (IOException e) {
                    error("Error on generating source code.", element);
                } catch (BaseCompilerException e) {
                    error(e.getMessage(), element);
                }
            }
        }
        return false;
    }

    private void processTable(Element element) throws IOException, BaseCompilerException {
        TableModel tableModel = new TableModel(element);

        SchemeContext schemeContext = new SchemeContext(tableModel);
        ConverterContext converterContext = new ConverterContext(schemeContext);

        generate(schemeContext);
        generate(converterContext);
    }

    private void generate(BaseTemplateContext templateContext) throws IOException {
        JavaFileObject jfo = processingEnv
                .getFiler()
                .createSourceFile(templateContext.getGenerateName());

        BufferedWriter bw = new BufferedWriter(jfo.openWriter());
        String content = templateContext.toString();
        bw.append(content);
        bw.newLine();
        bw.close();
    }

    @Override
    public Set<String> getSupportedAnnotationTypes() {
        Set<String> annotations = new HashSet<>();
        annotations.add(Table.class.getName());
        annotations.add(DbSkipField.class.getName());
        annotations.add(DbColumn.class.getName());
        return annotations;
    }

    @Override
    public SourceVersion getSupportedSourceVersion() {
        return SourceVersion.latestSupported();
    }

    private void error(String message, Element element) {
        processingEnv.getMessager().printMessage(Diagnostic.Kind.ERROR, message, element);
    }
}

redpajama_set_name: RedPajamaGithub


And the 2015 FootballScoop FBS Video of the Year is….
We wanted to choose someone else. We really did. But in the end, Colorado once again produced the best video college sports had to offer in 2015.
Following last year's triumphant "Seasons" epic, Colorado provided a sequel in "Forever" that matched its predecessor in scope and execution. "Forever" successfully and elegantly informs recruits what life will be like when they are Colorado football players while also appealing to the fans who always wished they could be. The cinematography, editing, writing and overall concept are simply a step above the rest of the industry.
The FootballScoop staff would like to issue a congratulations to Jamie Guy and the rest of his staff and Boulder, and another congratulations to the five other finalists – Appalachian State, Clemson, Colorado State, Georgia and Mississippi State – as well the dozens of other entrants.


text:
Hilario Ascásubi (n. 14 ianuarie 1807 - d. 17 noiembrie 1875) a fost poet argentinian.

Opera
 1846: Paulino Lucero ("Paulino Lucero");
 1851: Santos Vega sau germenii din flare ("Santos Vega o los mellizos de la flor");
 1853: Aniceto cocoșul ("Aniceto et Gallo").

Bibliografie
 Danțiș, Gabriela - Scriitori străini, Editura Științifică și Enciclopedică București, 1981

Legături externe
  Biografie la Los-Poetas.com
  Poeme
  Biografie la FolkloreDelNorte.com.ar

Nașteri în 1807
Decese în 1875
Scriitori argentinieni

redpajama_set_name: RedPajamaWikipedia


Represents a collection of Trend Lines of a specific series.
An object of the TrendLineCollection type is returned by the FinancialIndicators.TrendLines property, which is now obsolete. The TrendLineCollection class isn't used anymore, and is only retained for backward compatibility.
Now, individual TrendLine objects are stored in the IndicatorCollection (along with other indicator types available), returned by the XYDiagram2DSeriesViewBase.Indicators property.
For more information, refer to Trend Lines.


Every year I declare to myself that this year, is the year I will learn to name the constellations in the sky.
The hand-printed ship sailing at midnight is just breathtaking. Oversized drape fit long-sleeved T-Shirt with round neck and relaxed fit has an all over stars/constellation print with the Sailing ship hand-print to rear of top.
Harry & Polly are the designers behind Draw In Light. Harry met Polly in a West London hospital, 20th April 1985. This was the first day of their 25 year friendship. Learning to walk, talk, draw and dress up together. The two have had a unique creative bond since that day. The pair studied textiles for fashion with business at the University of Brighton, graduating in the summer of 2008. Draw In Light was formed in December 2009. Harry and Polly now work from their studio in East London.
You can see their latest collection at the wonderful Young British Designers.
The long dress with the wave print is especially lovely!


(1) For delivery within Germany we charge shipping costs of 7.00 € (excl. VAT) per order. For delivery to Austria and Benelux we charge 15.00 € (excl. VAT), for Italy, Poland, Czech Republic, France, UK and Denmark we charge 20,00 € (excl. VAT) per order. Spain and Sweden € 25.00 (excl. VAT) per order.
Switzerland and all other countries as agreed with DHL, UPS or FedEx.
(1) Deliveries within the EU are carried out by DHL. Other countries as agreed (UPS or FedEx).
(2) If an article is not available, we may withdraw from the contract. If there is no comparable product available, or you do not want, that we supply a comparable product, payments already made will be refunded without delay.
(3) If the delivery of the goods fails after three unsuccessful delivery attempts we may withdraw from the contract. Payments already made will be refunded without delay less all costs incurred by us.


Carrie Oliver could be living in Bismarck or Dickinson.
Lived in Billings and Bridger, MT.
Keller, North Richland Hills, Mansfield, and Arlington, TX.
Possible Associates Carrie Ann Oliver could have been associated with Jacob Dee Baker, Teresa Lynn Bills, Barbara Jean Grayson, Daniel L Hall, Daniel Michael Hall, and Evelyn M Hall.
Lived in Kilgore, Gladewater, Longview, and Prosper, TX.
Possible Associates Carrie Oliver could have been associated with Ryan Christopher Barrand, Alicia Renee Daniel, Isaac Ross Kimberlin, Darlene Larson Perry, Kurt Glenn Russell, and Rachel Michelle Willeford.
Possible Associates Carrie Oliver could have been associated with Clifford Alan Larson, Eric Martin Larson, Nikole Lynn Larson, Dawn Marie Moyar, and Georgia Kay Rector.


C ( Computer program language) I. Science– Mathematics– Computer programs.
Numerical analysis– Computer programs. Numerical recipes in c pdf 下载. Pdf, 微盘是一款简单易用的网盘, 提供超大免费云存储空间, 支持电脑、 手机 等终端的文档存储、 在线阅读、 免费下载、 同步和分享是您工作、 学习、 生活 的必备工具! 通过新浪微盘下载 中文_ Numerical recipes in c.
– dcA catalog record for this book is. Numerical Recipes in C ( PDF) Front Matter Contents, Prefaces xi Legal Matters xvi Computer Programs by Chapter Section xix 1 Preliminaries. Press, William H.
The product of a singular collaboration amongst 4 main scientists in educational analysis business, Numerical Recipes is a complete textual content reference work on scientific mple page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING ( ISBNCopyright ( Cby Cambridge University Press.
The Mirror Site ( 2) - PDF ( 949 pages, 10. 1 MB) - are cipes, Numerical Recipes Software. We are one of the oldest continuously operating sites on the Web, with the historic former domain nr.
com dating back to 1993, one of the first 25, 000 domains in the rmation should be addressed to Numerical Recipes Software, P. Box 380243, Cambridge, MAUSA), email or fax.
A catalog record for this book is available from the British Library. Numerical Recipes in C The Art of Scientific Computing Second Edition William H. Press Harvard- Smithsonian Center for Astrophysics Saul A. Teukolsky Department of Physics, Cornell University.
Numerical recipes in C( 英文). PDF 1187页 本文档一共被下载: 次, 您可全文免费在线阅读后下载本文档。. Numerical recipes in C : the art of scientific computing / William H.
Includes bibliographical references ( p.


High temperature products for stationary systems require crucial criteria, such as maintenance and the ability to enable the user to assemble and disassemble our products, whilst also following close restrictions and legal requirements. This process also involves high quality control within the entire product life cycle to ensure it meets professional association regulations. These factors play a major part in ensuring the product is safe and the product has increased performance efficiency and reduced operating costs.
Soft jackets are more predominantly used for this application, as they are easily removable to allow for ease of maintenance. Not only bespoke soft insulation jackets be required, but the design may require a permanently fixed shield. This custom made product is a fixed stainless steel shell that encloses the insulation onto to the required surface, no matter how complex. Due to high precision of these systems, it can be designed within close parameters to accommodate the close proximity of the generators.


text:
\section{Acknowledgment}

	I would like to thank Scott Aaronson, Adam Bouland, Dhiraj Holden and Prashant Vasudevan for several helpful discussions during this work, Ruosong Wang for many comments on an early draft of this paper, Justin Thaler for the suggestion on the application in hardness amplification for polynomial approximation, and Mika G{\"{o}}{\"{o}}s and Thomas Watson for pointing out an issue in the proof of Theorem~\ref{theo:hard-adapt-postbpp}.

	\bibliographystyle{plainurl}

\section{Preliminaries for the appendix}

\subsection{Conical juntas}
We first introduce the definition for conical juntas (cf.~\cite{goos2015rectangles}), which will be used frequently in this appendix.

Let $x=x_{1}\ldots x_{M}\in\left\{  0,1\right\}  ^{M}$ be a string. \ Then a
\textit{literal} is a term of the form $x_i$ or $1-x_i$, and a
$k$-\textit{term }is a product of $k$ literals (each involving a different
$x_{i}$), which is $1$ if the literals all take on prescribed values and $0$ otherwise.

\begin{defi}
	A $T$-conical junta $h$ is a non-negative linear combination of $T$-terms, i.e., $h(x) := \sum_{i} \alpha_i \cdot C_i(x)$, where for each $i$ we have $\alpha_i \ge 0$ and $C_i$ is a $T$-term. We also define $\mathsf{weight}(h) := \sum_i \alpha_i$.
\end{defi}

The following lemma shows that conical juntas are more powerful than randomized decision trees.

\begin{lem}[Essentially Theorem 15 in~\cite{buhrman2002complexity}]\label{lm:conical-junta}
	The acceptance probability of a $T$-query randomized decision tree $\mathcal{T}$ can be represented by a $T$-conical junta $h$ with $\mathsf{weight}(h) \le 2^T$.
\end{lem}

\subsection{Complexity classes and their query complexity analogues}

We introduce the complexity classes: \textsf{SBP}, \textsf{SBQP}, $\textsf{PostBPP}$ ($\mathsf{BPP_{path}}$) here, and define their analogues in query complexity along the way.

\subsubsection{$\textsf{SBP}$ and $\SBP^{\dt}$}

Now we recall the definition of $\textsf{SBP}$, there are several equivalent definitions for $\textsf{SBP}$ in \cite{bohler2006error} (see Proposition 21), we use the most convenient one here.

\begin{defi}
	$\textsf{SBP}$ (defined by B{\"o}hler, Gla{\ss}er and Meister~\cite{bohler2006error}) is the class of languages $L\subseteq\left\{
	0,1\right\}  ^{\ast}$\ for which there exists a $\mathsf{BPP}$\ machine $M$ and a polynomial $p$, such that for all inputs $x$:

	\begin{enumerate}
		\item[(i)] $x\in L\Longrightarrow\Pr\left[  M\left(  x\right)  \text{ accepts}\right]  \geq 2^{-p(|x|)}$.

		\item[(ii)] $x\notin L\Longrightarrow\Pr\left[  M\left(  x\right)  \text{
			accepts}\right]  < 2^{-p(|x|)-1}$.
	\end{enumerate}
\end{defi}

Then we define the query complexity analogue of $\textsf{SBP}$ in the standard way.

\begin{defi}\label{defi:SBPdt}
	Let $f:D \to \{0,1\}$ with $D \subseteq \{0,1\}^M$ be a partial function. We say a randomized decision tree $\mathcal{T}$ $\textsf{SBP}$-computes $f$ if
	$$
	\Pr[\mathcal{T}(x) = 1] > 2 \cdot \Pr[\mathcal{T}(y) = 1]
	$$

	for all $x \in f^{-1}(1)$ and $y \in f^{-1}(0)$.

	We define $\SBP^{\dt}(f)$ as the minimum of $\mathcal{C}(\mathcal{T})$ over all $\mathcal{T}$ $\textsf{SBP}$-computing $f$.

	And we simply let $\coSBP^{\dt}(f) := \SBP^{\dt}(\neg f)$.
\end{defi}

It may seem strange at first that there is no $\log_2(1/\alpha)$ term in our definition of $\SBP^{\dt}(f)$. Actually, one can show that having the $\log_2(1/\alpha)$ term or not would not change the partial function class $\SBP^{\dt}$: the following lemma shows that whenever we have a randomized decision tree $\mathcal{T}$ $\textsf{SBP}$-computing a function $f$, $\mathcal{T}$ can be made to $\textsf{SBP}$-compute $f$ with a reasonable probability gap.

\begin{lem}[Proposition 33 in~\cite{goos2015rectangles}]
	Let $f:D \to \{0,1\}$ with $D \subseteq \{0,1\}^M$ be a partial function. Suppose $d=\SBP^{\dt}(f)$. Then there is a randomized decision tree $\mathcal{T}$ $\textsf{SBP}$-computing $f$ and a real number $\alpha$, such that
	$$
	\Pr[\mathcal{T}(x) = 1] > 2 \cdot \alpha \text{ and } \Pr[\mathcal{T}(y) = 1] \le \alpha \text{ and } \alpha \ge 2^{-(d+1)} \binom{n}{d}^{-1}
	$$
	for all $x \in f^{-1}(1)$, $y \in f^{-1}(0)$.
\end{lem}
\subsubsection{$\textsf{PostBPP}$ and $\PostBPP^{\dt}$}

In this subsection we review the definition of $\textsf{PostBPP}$, and define its analogue in query complexity.

Roughly speaking, $\textsf{PostBPP}$ consists of the computational problems can be solved in probabilistically polynomial time, given the ability to {\em postselect} on an event (which may happen with a very small probability). Formally:

\begin{defi}
	$\textsf{PostBPP}$ (defined by Han, Hemaspaandra, and Thierauf \cite{han1997threshold}\footnote{In the original paper it is called $\mathsf{BPP_{path}}$.}) is the class of languages $L\subseteq\left\{
	0,1\right\}  ^{\ast}$\ for which there exists a $\mathsf{BPP}$\ machine $M$,
	which can either \textquotedblleft succeed\textquotedblright\ or
	\textquotedblleft fail\textquotedblright\ and conditioned on succeeding either
	\textquotedblleft accept\textquotedblright\ or \textquotedblleft
	reject,\textquotedblright\ such that for all inputs $x$:

	\begin{enumerate}
		\item[(i)] $\Pr\left[  M\left(  x\right)  \text{ succeeds}\right]  >0$.

		\item[(ii)] $x\in L\Longrightarrow\Pr\left[  M\left(  x\right)  \text{ accepts
		}|~M\left(  x\right)  \text{ succeeds}\right]  \geq\frac{2}{3}$.

		\item[(iii)] $x\notin L\Longrightarrow\Pr\left[  M\left(  x\right)  \text{
			accepts }|~M\left(  x\right)  \text{ succeeds}\right]  \leq\frac{1}{3}$.
	\end{enumerate}
\end{defi}

$\PostBPP^{\dt}(f)$ can be defined similarly.

\begin{defi}\label{defi:PostBPPdt}
	Now we allow a randomized decision tree to output a failure mark $*$ besides $0$ and $1$.

	Let $f:D \to \{0,1\}$ with $D \subseteq \{0,1\}^M$ be a partial function. We say a randomized decision tree $\mathcal{T}$ $\textsf{PostBPP}$-computes $f$ if

	$$
	\Pr[\mathcal{T}(x) = 1] \ge 2 \cdot \Pr[\mathcal{T}(x) = 0] \text{ and } \Pr[\mathcal{T}(y) = 0] \ge 2 \cdot \Pr[\mathcal{T}(y) = 1]
	$$

	for all $x \in f^{-1}(1)$ and $y \in f^{-1}(0)$.

	Fix a $\mathcal{T}$ $\textsf{PostBPP}$-computing $f$, let $\alpha$ be the maximum real number such that
	$$
	\Pr[\mathcal{T}(x) \ne *] \ge \alpha
	$$

	for all $x \in D$.

	Then we define $\PostBPP^{\dt}(\mathcal{T};f) = C(\mathcal{T}) + \log_2(1/\alpha)$ for $\mathcal{T}$ $\textsf{PostBPP}$-computing $f$, and $\PostBPP^{\dt}(f)$ as the minimum of $\PostBPP^{\dt}(\mathcal{T};f)$ over all $\mathcal{T}$ $\textsf{PostBPP}$-computing $f$.
\end{defi}

\subsubsection{$\textsf{SBQP}$ and $\SBQP^{\dt}$}
In this subsection we review the definition of $\textsf{SBQP}$, and define its analogue in query complexity. Roughly speaking, $\textsf{SBQP}$ is just the quantum analogue of $\textsf{SBP}$.

\begin{defi}
	$\textsf{SBQP}$ (defined by Kuperberg~\cite{kuperberg2009hard}) is the class of languages $L\subseteq\left\{
	0,1\right\}  ^{\ast}$\ for which there exists a polynomial-time quantum algorithm $M$ and a polynomial $p$, such that for all inputs $x$:

	\begin{enumerate}
		\item[(i)] $x\in L\Longrightarrow\Pr\left[  M\left(  x\right)  \text{ accepts}\right]  \geq 2^{-p(|x|)}$.

		\item[(ii)] $x\notin L\Longrightarrow\Pr\left[  M\left(  x\right)  \text{
			accepts}\right]  \leq 2^{-p(|x|)-1}$.
	\end{enumerate}
\end{defi}

Then we define its query complexity analogue.

\begin{defi}\label{defi:SBQPdt}
	Let $f:D \to \{0,1\}$ with $D \subseteq \{0,1\}^M$ be a partial function. We say a quantum query algorithm $\mathcal{Q}$ $\textsf{SBQP}$-computes $f$ if

	$$
	\Pr[\mathcal{Q}(x) = 1] \ge 2 \cdot \Pr[\mathcal{Q}(y) = 1] \text{ and }
	\Pr[\mathcal{Q}(x) = 1] > 0
	$$

	for all $x \in f^{-1}(1)$ and $y \in f^{-1}(0)$.

	Fix a $\mathcal{Q}$ $\textsf{SBQP}$-computing $f$, let $\alpha$ be the maximum real number such that

	$$
	\Pr[\mathcal{Q}(x) = 1] \ge 2\alpha \text{ and } \Pr[\mathcal{Q}(y) = 1] \le \alpha
	$$

	for all $x \in f^{-1}(1)$ and $y \in f^{-1}(0)$.

	Then we define $\SBQP^{\dt}(\mathcal{Q};f) = C(\mathcal{Q}) + \log_2(1/\alpha)$ for $\mathcal{Q}$ $\textsf{SBQP}$-computing $f$ and $\SBQP^{\dt}(f)$ as the minimum of $\SBQP^{\dt}(\mathcal{Q};f)$ over all $\mathcal{Q}$ $\textsf{SBQP}$-computing $f$.

	And we simply let $\coSBQP^{\dt}(f) := \SBQP^{\dt}(\neg f)$.
\end{defi}

\subsubsection{$\textsf{PostBQP}$ and $\PostBQP^{\dt}$}
$\textsf{PostBQP}$ is defined similarly as $\textsf{PostBPP}$, just replaced the $\textsf{BPP}$ machine by a polynomial time quantum algorithm. And $\PostBQP^{\dt}(f)$ is defined in the same way as $\textsf{PostBPP}(f)$ except for changing the randomized decision tree $\mathcal{T}$ to a quantum query algorithm $\mathcal{Q}$.

\section{Missing proofs in Section~\ref{sec:pre}}

\begin{proofof}{Theorem~\ref{theo:eq-AZPP-mdega}}
	For the first claim, suppose $\AzPP^{\dt}(f)=d$, then there exists a $T$-query randomized decision tree $\mathcal{T}$ and a constant $\alpha>0$, such that
	\begin{itemize}
		\item $\Pr[\mathcal{T}(x)=1] \ge 1/2$ for all $x \in D$.
		\item $\Pr[\mathcal{T}(x)=1] - 1/2 \ge 2 \alpha$ and $\Pr[\mathcal{T}(y)=1] - 1/2 \le \alpha$ for all $x \in f^{-1}(1)$ and $y \in f^{-1}(0)$.
		\item $T$ + $\log_2(1/\alpha) = d$.
	\end{itemize}

	Let $h$ be the conical junta representing the acceptance probability of $\mathcal{T}$, we have $\mathsf{weight}(h) \le 2^T$ by Lemma~\ref{lm:conical-junta}.

	By expanding every $T$-term into $2^T$ monomials, we can further represent $h$ by a polynomial $p_h$ with $\mathsf{weight}(p_h) \le 2^{2T}$.

	Now, we define the polynomial
	$$p(x) := \frac{1}{2\alpha} \cdot (p_h(x)-1/2).$$

	We claim that $p$ one-sided approximates $f$. Indeed, when $f(x)=0$, we have $p_h(x) \in [1/2,1/2+\alpha]$, hence $p(x) \in [0,1/2]$; and when $f(x) = 1$, we have $p_h(x) \ge 1/2+2\alpha$, hence $p(x) \ge 1$.

	Moreover,
	$$\mathsf{weight}(p) \le (\mathsf{weight}(p_h) + 1/2) \cdot \frac{1}{2\alpha} \le 2^{2T}/\alpha,$$

	the last inequality holds as $\alpha < 1/4$.

	Hence
	\begin{align*}
	\qquad\qquad\qquad\qquad\widehat{\mathrm{deg}}_{+}(f) &\le \max \{\deg(p),\log_2(\mathsf{weight}(p))\} \\&\le \max\{T, 2T + \log_2(1/\alpha)\} \le 2d = 2 \cdot \AzPP^{\dt}(f).
	\end{align*}

	For the second claim, suppose $\widehat{\mathrm{deg}}_{+}(f)=d$, then there exists a $T$-degree polynomial $p$ one-sided approximating $f$ such that $T \le d$ and $\mathsf{weight}(p) \le 2^d$.

	Let $p(x) = \sum_{i=1}^{m} a_i \cdot M_i(x)$ and $S = \mathsf{weight}(p) = \sum_{i=1} |a_i|$, such that for each $i$, $a_i \in \mathbb{R}$ and $M_i$ is a unit monomial (i.e., $M_i(x) := x_{i_1}x_{i_2}\cdots x_{i_k}$).

	Consider the following algorithm:

	\begin{itemize}
		\item Pick an integer $i \in [m]$ by selecting $j$ with probability $|a_j| / S$.
		\item Query all the variables involved in $M_i$ to calculate $M_i(x)$.
		\item If $M_i(x) = 1$, accept if $a_i > 0$ and reject otherwise.
		\item If $M_i(x) = 0$, accept with probability $1/2$.
	\end{itemize}

	Clearly, as $p$ is of degree $T$, the above algorithm can be implemented by a $T$-query randomized decision tree $\mathcal{T}$.

	Now we analyze the acceptance probability of $\mathcal{T}$ on an input $x$. We can see
	$$
	\Pr[\mathcal{T}(x) = 1] = \sum_{i} \frac{1+M_i(x) \cdot a_i/|a_i|}{2} \cdot \frac{|a_i|}{S} = \frac{1}{2} + p(x) \cdot \frac{1}{2S}.
	$$

	Which means, when $f(x) = 0$, we have $p(x) \in [0,1/2]$, hence $\frac{1}{2} \le \Pr[\mathcal{T}(x) = 1] \le \frac{1}{2} + \frac{1}{4S}$; and when $f(x) = 1$, we have $p(x) \ge 1$, therefore $\frac{1}{2} \le \Pr[\mathcal{T}(x) = 1] \le \frac{1}{2} + \frac{1}{2S}$. So we can take $\alpha = \frac{1}{4S}$ and we have
	$$\AzPP^{\dt}(f) \le \AzPP^{\dt}(f;\mathcal{T}) \le T + \log_2(4S) = T + 2 + \log_2(\mathsf{weight}(p)) \le 2 \cdot \widehat{\mathrm{deg}}_{+}(f) + 2.$$

	This completes the proof.

\end{proofof}

\section{Missing proofs in Section~\ref{sec:quantum}}

\begin{proofof}{Lemma~\ref{lm:help-1}}
	Suppose not, let $p$ be a degree-$T$ polynomial computing $f$, and satisfies $\mathsf{weight}(p) \le 2^{T}$ and $\max_{ x \in f^{-1}(0)} -p(x) \le 2 \cdot \min_{y \in f^{-1}(1)} p(y)$.

	Let $C = \max_{ x \in f^{-1}(0)} -p(x)$, consider the following polynomial
	$$q(x) := \frac{2}{3}\cdot (p(x)/C + 1).$$
	We can see that when $f(x) = 0$, we have $p(x) \in [-C,-1]$, hence $q(x) \in [0, \frac{2}{3}]$; and when $f(x) = 1$, we have $p(x) \ge \frac{1}{2} \cdot C$, therefore $q(x) \ge 1$. Which means $q$ one-sided approximates $f$ with error constant $2/3$.

	Also, we have $\mathsf{weight}(q) \le \mathsf{weight}(p)\cdot \frac{2}{3C} + \frac{2}{3} \le \mathsf{weight}(p)$ as $C \ge 1$. So $\max\{\mathrm{deg}(q),\log_2(\mathsf{weight}(q))\} \le T$, contradiction to the fact that $\widehat{\mathrm{deg}}_{+}^{2/3}(f) > T$.
\end{proofof}

\begin{proofof}{Lemma~\ref{lm:pps-cons}}
	By our assumption, there exists a $t$-query randomized decision tree $\mathcal{T}$ and a real number $\alpha > 0$ such that

	\begin{itemize}
		\item when $f(x) = 1$, $\Pr[\mathcal{T}(x) = 1] \ge \frac{1}{2} + \alpha$.
		\item when $f(x) = 0$, $\Pr[\mathcal{T}(x) = 1] \le \frac{1}{2} - \alpha$.
		\item $t + \log_2(1/\alpha) \le T$.
	\end{itemize}

	Let $h$ be the conical junta representing the accepting probability of $\mathcal{T}$. We have $\mathsf{weight}(h) \le 2^t$.

	By expanding every $t$-term into $2^t$ monomials, we can further represent $h$ by a polynomial $p_h$ with $\mathsf{weight}(p_h) \le 2^{2t}$. Now we define $p(x) := (p_h(x)-\frac{1}{2})/\alpha$. Clearly $p$ computes $f$.

	Moreover, $\mathsf{weight}(p) \le (2^{2t} + \frac{1}{2} ) \cdot (1/\alpha) \le 2^{2T}$, which completes the proof.

\end{proofof}
\section{Proof for the classical case}\label{sec:classical}
In this section we prove Theorem~\ref{theo:ada-postbpp} and Theorem~\ref{theo:hard-adapt-postbpp}.

\subsection{$\SBP^{\dt}$ by conical juntas}

We first show when considering the $\SBP^{\dt}$, we can work with a {\em conical junta} instead of a randomized decision tree.

\begin{prop}\label{prop:equi-junta}
The definition of $\SBP^{\dt}(f)$ is unchanged if we replace the $T$-query randomized decision tree by a $T$-conical junta.
\end{prop}
\begin{proof}
We are going to show the existence of a $T$-query randomized decision tree $\mathcal{T}$ $\textsf{SBP}$-computing $f$ is equivalent to the existence of a $T$-conical junta $h$ $\textsf{SBP}$-computing $f$.

Suppose there exists a $T$-query randomized decision tree $\mathcal{T}$ $\textsf{SBP}$-computing $f$, then the acceptance probability of $\mathcal{T}$ can be presented as a $T$-conical junta by Lemma~\ref{lm:conical-junta}.

For the other direction, suppose there exists a $T$-conical junta $h$ $\textsf{SBP}$-computing $f$, let $h(x) := \sum_{i} \alpha_i \cdot C_i(x)$. Consider the following algorithm: let $P = \sum_i \alpha_i$, we pick a random $T$-term by selecting $C_i$ with probability $\alpha_i/P$ and accept if $C_i$ evaluates to $1$ on the given input. It is not hard to see the above algorithm can be represented by a $T$-query randomized decision tree, and it $\textsf{SBP}$-computes $f$.
\end{proof}

\subsection{A dual characterization for $\SBP^{\dt}$}

We first establish an equivalent dual condition of a function having large $\SBP^{\dt}$ complexity.

\begin{lem}\label{lm:equivalent-cond}
	Let $f:D \to \{0,1\}$ with $D \subseteq \{0,1\}^M$ be a partial function, $T$ be a positive integer, $\SBP^{\dt}(f) > T$ if and only if there exist two distributions $\mathcal{D}_0$ and $\mathcal{D}_1$ supported on $f^{-1}(0)$ and $f^{-1}(1)$ respectively, such that

	$$
	C(\mathcal{D}_0) \ge \frac{1}{2} \cdot C(\mathcal{D}_1) \text{ for any $T$-term $C$,}
	$$

	where $C(\mathcal{D}_i)$ is defined as $\mathbb{E}_{x \sim \mathcal{D}_i}[C(x)]$ for $i \in \{0,1\}$.
\end{lem}
\begin{proof}
	let $\mathcal{H}_T$ be the set of all $T$-conical juntas on $\{0,1\}^M$, and $f^i:=f^{-1}(i)$ for $i \in \{0,1\}$, by Proposition~\ref{prop:equi-junta}, $\SBP^{\dt}(f) > T$ is equivalent to

	$$
	\min_{h \in \mathcal{H}_T} \max_{(x,y) \in f^0\times f^1} \left(h(x) - \frac{1}{2} \cdot h(y) \right) \ge 0.
	$$

	Then by the minimax theorem, the above is again equivalent to

	$$
	\max_{\mathcal{D}_{xy} \text{ on }f^0\times f^1} \min_{h \in \mathcal{H}_T}  \mathbb{E}_{(x,y) \sim \mathcal{D}_{xy}}\left(h(x) - \frac{1}{2} \cdot h(y) \right) \ge 0.
	$$

	where $\mathcal{D}_{xy}$ is a distribution on $f^0 \times f^1$.

	Observe that we can further take $\mathcal{D}_{xy}$ to be a product distribution and we can assume $h$ is just a $T$-term. Putting everything together, $\SBP^{\dt}(f) > T$ is equivalent to

	$$
	\max_{\mathcal{D}_0 \text{ on } f^0} \max_{\mathcal{D}_1 \text{ on } f^1} \min_{C\text{ is a $T$-term}} \mathbb{E}_{x \sim \mathcal{D}_0, y \sim \mathcal{D}_1} \left(C(x) - \frac{1}{2} \cdot C(y) \right) \ge 0,
	$$
	where $\mathcal{D}_i$ is a distribution on $f^i$ for $i \in \{0,1\}$. This completes the proof.

\end{proof}

\begin{rem}
	Another way to prove the above lemma is to use strong duality in linear programming directly. We feel that our proof by minimax theorem is conceptually cleaner.
\end{rem}

The following corollary follows from the definition.

\begin{cor}\label{cor:equivalent-cond-coSBP}
	Let $f:D \to \{0,1\}$ with $D \subseteq \{0,1\}^M$ be a partial function, $T$ be a positive integer, $\coSBP^{\dt}(f) > T$ if and only if there exist two distributions $\mathcal{D}_0$ and $\mathcal{D}_1$ supported on $f^{-1}(0)$ and $f^{-1}(1)$ respectively, such that

	$$
	C(\mathcal{D}_1) \ge \frac{1}{2} \cdot C(\mathcal{D}_0) \text{ for any $T$-term $C$.}
	$$
\end{cor}

\subsection{Proof for Theorem~\ref{theo:ada-postbpp} and Theorem~\ref{theo:hard-adapt-postbpp}}

We first show Theorem~\ref{theo:hard-adapt-postbpp} implies Theorem~\ref{theo:ada-postbpp}.

\begin{proofof}{Theorem~\ref{theo:ada-postbpp}}
Suppose $\mathbf{f} \not\in \SBP^{\dt}$, the case that $\mathbf{f} \not\in \coSBP^{\dt}$ is similar.

Then there exists a sequence of function $\{f_i\}_{i=1}^{\infty} \subseteq \mathbf{f}$ such that $\SBP^{\dt}(f_i) > \log(\mathsf{len}(f_i))^{i}$. Then we consider the partial function sequence $\{ \mathsf{Ada}_{f_i,\lceil\log(\mathsf{len}(f_i)) \rceil} \}_{i=1}^{\infty} \subseteq \mathsf{Ada}_{\mathbf{f}}$.

By Theorem~\ref{theo:hard-adapt-postbpp}, we have
$$
\PostBPP^{\dt}(\mathsf{Ada}_{f_i,\lceil\log(\mathsf{len}(f_i)) \rceil}) > \min(\log(\mathsf{len}(f_i))^{i}/5,(\mathsf{len}(f_i)-1)/5).
$$

Note that $\mathsf{len}(\mathsf{Ada}_{f_i,\lceil\log(\mathsf{len}(f_i)) \rceil}) \le 2 \cdot \mathsf{len}(f_i)^2$, we can see $\mathsf{Ada}_{\mathbf{f}} \notin \PostBPP^{\dt}$ due to the above sequence.
\end{proofof}

Now we are going to prove Theorem~\ref{theo:hard-adapt-postbpp}. We say a pair of conical juntas $a(x)$ and $r(x)$ computes a function $f$ if it satisfies the following two conditions.

\begin{itemize}
	\item When $f(x)=1$, $a(x) \ge 5\cdot r(x)$ and $a(x) \ge 1$.
	\item When $f(x)=0$, $r(x) \ge 5\cdot a(x)$ and $r(x) \ge 1$.
\end{itemize}

In order to lower bound the $\PostBPP^{\dt}$ complexity of some functions, we introduce some consequences of a function having low $\PostBPP^{\dt}$ complexity.
\begin{lem}\label{lm:postbpp-cons}
	Let $f:D \to \{0,1\}$ with $D \subseteq \{0,1\}^M$ be a partial function, $T$ be a positive integer. Suppose $\PostBPP^{\dt}(f) \le T$, then there exist two $5T$-conical juntas $a(x)$ and $r(x)$ such that

	\begin{itemize}
		\item The pair of $a(x)$ and $r(x)$ computes $f$.
		\item $\max_{x \in \{0,1\}^M} a(x) \le 2^{5T+1}$ and $\max_{x \in \{0,1\}^M} r(x) \le 2^{5T+1}$.
	\end{itemize}
\end{lem}

\begin{proof}
	Amplifying the probability gap by taking the majority of $5$ independent runs, we get a randomized decision tree $\mathcal{T}$ such that
	\begin{itemize}
		\item $\PostBPP^{\dt}(\mathcal{T};f) \le 5T$.
		\item 	$
		\Pr[\mathcal{T}(x) = 1] \ge 5 \cdot \Pr[\mathcal{T}(x) = 0] \text{ and } \Pr[\mathcal{T}(y) = 0] \ge 5 \cdot \Pr[\mathcal{T}(y) = 1]
		$ for all $x \in f^{-1}(1)$ and $y \in f^{-1}(0)$.
	\end{itemize}

	Then we simply define $a(x)$ ($r(x)$) as $2^{5T+1}$ multiplies the acceptance (reject) probability of $\mathcal{T}$. $a(x)$ and $r(x)$ can be represented by $5T$-conical juntas by Lemma~\ref{lm:conical-junta}.

	Now we show $a(x)$ and $r(x)$ satisfy our conditions. The second condition follows directly from their definitions.
	For the first condition, when $f(x)=1$, we have $a(x) \ge 5 \cdot r(x)$ by their definitions, and since $\Pr[\mathcal{T}(x) \in \{0,1\}] \ge 2^{-5T}$ for all $x \in D$, $a(x) \ge 2^{5T+1} \cdot \frac{5}{6} \cdot 2^{-5T} \ge 1$. The case when $f(x)=0$ can be verified in the same way, and this completes the proof.
\end{proof}

Our proof proceed by a similar fashion as in Section~\ref{sec:quantum}, it again relies on the following two key lemmas.

\begin{lem}\label{lm:dist-exist-SBP}
Let $f:D \to \{0,1\}$ with $D \subseteq \{0,1\}^M$ be a partial function with $\SBP^{\dt}(f) > T$. Then for each integer $d$, there exist two distributions $\mathcal{D}_1^d$ and $\mathcal{D}_0^d$ supported on $\mathsf{Ada}_{f,d}^{-1}(1)$ and $\mathsf{Ada}_{f,d}^{-1}(0)$ respectively, such that $r(\mathcal{D}_0^d)> 2^{2^d} \cdot a(\mathcal{D}_1^d)$ for any $T$-conical juntas $a(x)$ and $r(x)$ computing $\mathsf{Ada}_{f,d}$.
\end{lem}

\begin{lem}\label{lm:dist-exist-coSBP}
Let $f:D \to \{0,1\}$ with $D \subseteq \{0,1\}^M$ be a partial function with $\coSBP^{\dt}(f) > T$. Then for each integer $d$, there exist two distributions $\mathcal{D}_1^d$ and $\mathcal{D}_0^d$ supported on $\mathsf{Ada}_{f,d}^{-1}(1)$ and $\mathsf{Ada}_{f,d}^{-1}(0)$ respectively, such that $a(\mathcal{D}_1^d) > 2^{2^d} \cdot a(\mathcal{D}_1^d)$ for any $T$-conical juntas $a(x)$ and $r(x)$ computing $\mathsf{Ada}_{f,d}$.
\end{lem}

Before proving Lemma~\ref{lm:dist-exist-SBP} and Lemma~\ref{lm:dist-exist-coSBP}, we show they imply Theorem~\ref{theo:hard-adapt-postbpp}.

\begin{proofof}{Theorem~\ref{theo:hard-adapt-postbpp}}
We first prove the case $\SBP^{\dt}(f) > T$. Suppose  $\PostBPP^{\dt}(\mathsf{Ada}_{f,d}) \le \min(T/5,(2^{d}-1)/5)$, by Lemma~\ref{lm:postbpp-cons}, there is a pair of $T$-conical juntas $a(x)$ and $r(x)$ computing $\mathsf{Ada}_{f,d}$ such that $\max_{x} r(x) \le 2^{2^d}$.

By Lemma~\ref{lm:dist-exist-SBP}, we have $r(\mathcal{D}_0^d) > 2^{2^d} \cdot a(\mathcal{D}_1^d) \ge 2^{2^d}$. Hence there must exist an $x$ such that $r(x) > 2^{2^d}$, contradiction.

Then case for $\coSBP^{\dt}(f) > T$ follows from exactly the same argument and Lemma~\ref{lm:dist-exist-coSBP}.
\end{proofof}

\subsection{Proof for Lemma~\ref{lm:dist-exist-SBP}}

Finally we prove Lemma~\ref{lm:dist-exist-SBP}, the proof for Lemma~\ref{lm:dist-exist-coSBP} is completely symmetric.

\begin{proofof}{Lemma~\ref{lm:dist-exist-SBP}}
	We are going to construct those distributions by an induction on $d$. Let $f_d := \mathsf{Ada}_{f,d}$ and $D_d$ be the domain of $f_d$.

	{\bf Construction of $\mathcal{D}_0$ and $\mathcal{D}_1$ from Lemma~\ref{lm:equivalent-cond}.}
	As $\SBP^{\dt}(f) > T$, by Lemma~\ref{lm:equivalent-cond}, there exist two distributions $\mathcal{D}_0$ and $\mathcal{D}_1$ supported on $f^{-1}(0)$ and $f^{-1}(1)$ respectively, such that
	$$
	h(\mathcal{D}_0) \ge \frac{1}{2} \cdot h(\mathcal{D}_1) \text{ for any $T$-conical junta $h$.}
	$$

	{\bf The base case: construction of $\mathcal{D}_0^0$ and $\mathcal{D}_1^0$.}
	The base case $d=0$ is very simple. $f_0$ is just the $f$ itself. We let $\mathcal{D}_1^0 = \mathcal{D}_1$ and $\mathcal{D}_0^0=\mathcal{D}_0$. Then we have $a(\mathcal{D}_0) \ge \frac{1}{2} \cdot a(\mathcal{D}_1)$. Also,  $r(\mathcal{D}_0)\ge 5 \cdot a(\mathcal{D}_0)$ as $\mathcal{D}_0$ is supported on $f^{-1}(0)$. Putting these facts together, we have $r(\mathcal{D}_0) > 2 \cdot a(\mathcal{D}_1)$, which completes the case for $d = 0$.

	{\bf Construction of $\mathcal{D}_0^0$ and $\mathcal{D}_1^0$ for $d > 0$.}
	For $d>0$, suppose that we have already constructed distributions $\mathcal{D}_0^{d-1}$ and $\mathcal{D}_1^{d-1}$ on inputs of $f_{d-1}$. Decompose the input to $f_d$ as $(w,x,y) \in D \times D_{d-1} \times D_{d-1}$ as in the definition, we claim that
	$$\mathcal{D}_{0}^d = (\ddd{0}{0}{0})\footnote{recall that ($\ddd{0}{0}{0})$ is interpreted as the product distribution $\mathcal{D}_0 \times \mathcal{D}_{0}^{d-1} \times \mathcal{D}_0^{d-1}$ on $ D \times D_{d-1} \times D_{d-1}$.}$$ and $$\mathcal{D}_{1}^d = (\ddd{1}{1}{1})$$ satisfy our conditions.

	{\bf Analysis of $\mathcal{D}_0^{d}$ and $\mathcal{D}_1^{d}$.}
	Note that $D_{i}^d$ is supported on $f_d^{-1}(i)$ for $i \in \{0,1\}$ from the definition. For a conical juntas $h(w,x,y)$ on $D \times D_{d-1} \times D_{d-1}$, We let
	$$h(\mathcal{D}_w,\mathcal{D}_x,\mathcal{D}_y) := \mathbb{E}_{w\sim \mathcal{D}_w, x \sim \mathcal{D}_x, y\sim \mathcal{D}_y}[h(w,x,y)]$$ for simplicity, where $\mathcal{D}_w,\mathcal{D}_x,\mathcal{D}_y$ are distributions over $D,D_{d-1},D_{d-1}$ respectively.

	We have to verify that
	$$
	r(\mathcal{D}_0^d) = r(\mathcal{D}_0,\mathcal{D}_0^{d-1},\mathcal{D}_0^{d-1}) > 2^{2^d} \cdot a(\mathcal{D}_1,\mathcal{D}_1^{d-1},\mathcal{D}_1^{d-1}) = 2^{2^d} \cdot a(\mathcal{D}_1^d).
	$$

	In the same way as in Section~\ref{sec:quantum}, we proceed by incrementally changing $(\ddd{0}{0}{0})$ into $(\ddd{1}{1}{1})$.

	{\bf Step 1: $(\ddd{0}{0}{0}) \Rightarrow (\ddd{0}{1}{0})$.}
	Consider the following two $T$-conical juntas on $x$:
	$$
	a_L(x) := a(\mathcal{D}_0,x,\mathcal{D}_0^{d-1}) =\mathbb{E}_{w \sim \mathcal{D}_0,y \sim \mathcal{D}_0^{d-1}} [a(w,x,y)],
	$$ and
	$$
	r_L(x) := r(\mathcal{D}_0,x,\mathcal{D}_0^{d-1}) = \mathbb{E}_{w \sim \mathcal{D}_0,y \sim \mathcal{D}_0^{d-1}} [r(w,x,y)].
	$$

	Note that for any fixed $W \in \mathbf{support}(\mathcal{D}_0)$ and any $Y \in \mathbf{support}(\mathcal{D}_0^{d-1})$, by the definition of $f_d$, the $T$-conical junta pair $a(W,x,Y)$ and $r(W,x,Y)$ must compute $f_{d-1}$. It is not hard to verify by linearity, that their expectations $a_L(x)$ and $r_L(x)$ also compute $f_{d-1}$.

	Therefore, plugging in $\mathcal{D}_0^{d-1}$ and $\mathcal{D}_1^{d-1}$, we have $r_L(\mathcal{D}_0^{d-1}) > 2^{2^{d-1}} \cdot a_L(\mathcal{D}_0^{d-1})$, which means
	$$r(\mathcal{D}_0,\mathcal{D}_0^{d-1},\mathcal{D}_0^{d-1}) > 2^{2^{d-1}} \cdot a(\mathcal{D}_0,\mathcal{D}_1^{d-1},\mathcal{D}_0^{d-1}).$$

	{\bf Step 2: $(\ddd{0}{1}{0}) \Rightarrow (\ddd{1}{1}{0})$.} Then, for each fixed $X,Y$, the polynomial $a_M(w) := a(w,X,Y)$ is a $T$-conical junta, so we have $a_M(\mathcal{D}_0) \ge \frac{1}{2} \cdot a_M(\mathcal{D}_1)$. Hence by linearity,
	$$
	a(\mathcal{D}_0,\mathcal{D}_1^{d-1},\mathcal{D}_0^{d-1}) \ge \frac{1}{2} \cdot a(\mathcal{D}_1,\mathcal{D}_1^{d-1},\mathcal{D}_0^{d-1}).
	$$

	Now, notice that $\mathcal{D}_1$ is supported on $f^{-1}(1)$, and $\mathcal{D}_0^{d-1}$ is supported on $f_{d-1}^{0}$, so $(\mathcal{D}_1,\mathcal{D}_1^{d-1},\mathcal{D}_0^{d-1})$ is supported on $f_d^{-1}(1)$, therefore
	$$
	a(\mathcal{D}_1,\mathcal{D}_1^{d-1},\mathcal{D}_0^{d-1}) \ge 5 \cdot r(\mathcal{D}_1,\mathcal{D}_1^{d-1},\mathcal{D}_0^{d-1}).
	$$

	{\bf Step 3: $(\ddd{1}{1}{0}) \Rightarrow (\ddd{1}{1}{1})$.} Finally, consider the polynomials on $y$ defined by
	$$
	a_{R}(y) := a(\mathcal{D}_1,\mathcal{D}_1^{d-1},y)
	\text{ and }
	r_{R}(y) := r(\mathcal{D}_1,\mathcal{D}_1^{d-1},y).
	$$
	By the same augment as above, they are also a pair of $T$-conical juntas computing $f_{d-1}$, so plugging in $\mathcal{D}_0^{d-1}$ and $\mathcal{D}_1^{d-1}$ again, we have $r_{R}(\mathcal{D}_0^{d-1}) > 2^{2^{d-1}} \cdot a_{R}(\mathcal{D}_1^{d-1})$, which means
	$$
	r(\mathcal{D}_1,\mathcal{D}_1^{d-1},\mathcal{D}_0^{d-1}) > 2^{2^{d-1}} \cdot a(\mathcal{D}_1,\mathcal{D}_1^{d-1},\mathcal{D}_1^{d-1}).
	$$

	Putting everything together, we have
	$$
	r(\mathcal{D}_0,\mathcal{D}_0^{d-1},\mathcal{D}_0^{d-1}) > (2^{2^{d-1}} \cdot \frac{1}{2} \cdot 5 \cdot 2^{2^{d-1}}) \cdot a(\mathcal{D}_1,\mathcal{D}_1^{d-1},\mathcal{D}_1^{d-1}) > 2^{2^d} \cdot a(\mathcal{D}_1,\mathcal{D}_1^{d-1},\mathcal{D}_1^{d-1}).
	$$

	This completes the proof.
\end{proofof}

\section{Introduction}

\subsection{Background}

The idea of postselection has been surprisingly fruitful in theoretical computer science and quantum computing~\cite{aaronson2011computational,drucker2009quantum,bremner2011classical}. Philosophically, it addresses the following question: if you believe in the Many-worlds interpretation\footnote{\url{https://en.wikipedia.org/wiki/Many-worlds_interpretation}} and can condition on a rare event (implemented by killing yourself after observing the undesired outcomes), then what would you be able to compute in a reasonable amount of time? The complexity classes $\textsf{PostBPP}$~\cite{han1997threshold} and $\textsf{PostBQP}$~\cite{aaronson2005quantum} are defined to represent the computational problems you can solve with the ability of postselection in a classical world or a quantum world.

However, even with that seemingly omnipotent power of postselection, your computational power is still bounded. It is known that $\textsf{PostBPP} \subseteq \textsf{PH}$~\cite{han1997threshold}, and (surprisingly) $\textsf{PostBQP} = \textsf{PP}$~\cite{aaronson2005quantum}. Hence, it seems quite plausible that even with the postselection power, you are still not able to solve a $\textsf{PSPACE-complete}$ problem, as it is widely believed that $\textsf{PH}$ and $\textsf{PP}$ are strictly contained in $\textsf{PSPACE}$.

Another more non-trivial (and perhaps unexpected) weakness of those postselection computation classes, is their inability to simulate {\em adaptive queries} to certain languages. For example, it is known that $\textsf{P}^{\textsf{NP}[O(\log n)]}$\footnote{$O(\log n)$ stands for the  $\textsf{P}$ algorithm can only make $O(\log n)$ queries to the oracle.} is contained in $\textsf{PostBPP}$~\cite{han1997threshold}, and this result relativizes. But there is an oracle separation between $\textsf{P}^{\textsf{NP}[\omega(\log n)]}$ and $\textsf{PostBQP}$~\cite{beigel1994perceptrons}. In other words, there is no relativized $\textsf{PostBQP}$ algorithm that can simulate $\omega(\log n)$ adaptive queries to a certain language in $\textsf{NP}$. In contrast, we know that $\textsf{P}^{\parallel \textsf{NP}} \subseteq \textsf{PostBPP} \subseteq \textsf{PP}$ \cite{han1997threshold}, hence they are capable of simulating {\em non-adaptive} queries to $\textsf{NP}$.

Then a natural question follows:

\begin{question}\label{ques:comp-ques}
What is the limit of the abilities of these postselection classes on simulating adaptive queries to certain languages? More specifically, is there any characterization of the complexity class $\mathcal{C}$ such that $\textsf{P}^{\mathcal{C}}$ is contained in $\textsf{PostBPP}$ or $\textsf{PostBQP}$?
\end{question}

Arguably, a complete answer to this problem seems not possible at the present time: even determining whether $\textsf{P}^{\textsf{NP}} \subseteq \textsf{PP}$ is already extremely hard, as showing $\textsf{P}^{\textsf{NP}} \subseteq \textsf{PP}$ probably requires some new non-relativized techniques, and proving $\textsf{P}^{\textsf{NP}} \not\subset \textsf{PP}$ implies $\textsf{PH} \not\subset \textsf{PP}$, which is a long-standing open problem.

\subsection{Relativization and the analogous question in query complexity}

So in this paper, inspired by the oracle separation in~\cite{beigel1994perceptrons}, we study this problem from a relativization point of view. {\em Relativization}, or {\em oracle separations} are ultimately about the {\em query complexity}. Given a complexity class $\mathcal{C}$, there is a canonical way to define its analogue in query complexity: partial functions which are computable by a {\em non-uniform} $\mathcal{C}$ machine with $\operatorname*{polylog}(n)$ queries to the input. For convenience, we will use $\mathcal{C}^{\textsf{dt}}$ to denote the query complexity version of $\mathcal{C}$. We adopt the convention that  $\mathcal{C}^{\textsf{dt}}$ denotes the query analogue of $\mathcal{C}$, while $\mathcal{C}^{\textsf{dt}}(f)$ denotes the $\mathcal{C}^{\textsf{dt}}$ complexity of the partial function $f$.

\newcommand{\mathsf{len}}{\mathsf{len}}

For a partial function $f$, we use $\mathsf{len}(f)$ to denote its input length. We say a family of partial functions $\mathbf{f} \in \mathcal{C}^{\textsf{dt}}$, if $\mathcal{C}^{\textsf{dt}}(f) = O(\operatorname*{polylog}(\mathsf{len}(f)))$ for all $f \in \mathbf{f}$.

In order to study this question in the query complexity setting, given a partial function $f$, we need to define its adaptive version.

\begin{defi}[Adaptive Construction]
	Given a function $f :D \to \{0,1\}$ with $D \subseteq \{0,1\}^M$ and an integer $d$, we define $\mathsf{Ada}_{f,d}$, its depth $d$ adaptive version, as follows:

	$$
	\begin{array}{ c c }
	\mathsf{Ada}_{f,0} := f \quad \text{and} &
	\begin{array}{ c }
	\mathsf{Ada}_{f,d}: D \times D_{d-1} \times D_{d-1} \to \{0,1\}\\
	\mathsf{Ada}_{f,d}(w,x,y) := \begin{cases}
	\mathsf{Ada}_{f,d-1}(x) & \quad f(w) = 0\\
	\mathsf{Ada}_{f,d-1}(y) & \quad f(w) = 1\\
	\end{cases}
	\end{array}
	\end{array}
	$$
	where $D_{d-1}$ denotes the domain of $\mathsf{Ada}_{f,d-1}$.

	The input to $\mathsf{Ada}_{f,d}$ can be encoded as a string of length $(2^{d+1}-1)\cdot M$. Thus, $\mathsf{Ada}_{f,d}$ is a partial function from $D^{(2^{d+1}-1)} \to \{0,1\}$.
\end{defi}

Then, given a family of partial function $\mathbf{f}$, we define $\mathsf{Ada}_{\mathbf{f}} := \{ \mathsf{Ada}_{f,d} \ |\  f \in \mathbf{f}, d \in \mathbb{N} \}$.

Notice that when you have the ability to adaptively solve $d+1$ queries to $f$ (or with high probability), then it is easy to solve $\mathsf{Ada}_{f,d}$.
Conversely, in order to solve $\mathsf{Ada}_{f,d}$, you need to be able to adaptively answer $d+1$ questions to $f$, as even {\em knowing what is the right $i^{th}$ question to answer} requires you to correctly answer all the previous $i-1$ questions.

Now, everything is ready for us to state the analogous question in query complexity.

\begin{question}\label{ques:query-ques}
	What is the characterization of the partial functions family $\mathbf{f}$ such that $\mathsf{Ada}_{\mathbf{f}} \in \PostBPP^{\dt}$ ($\PostBQP^{\dt}$)?
\end{question}

There are at least two reasons to study Question~\ref{ques:query-ques}. First, it is an interesting question itself in query complexity. Second, an answer to Question~\ref{ques:query-ques} also completely characterizes the limitation on the {\em relativized techniques} for answering Question~\ref{ques:comp-ques}, i.e., the limitation of relativized methods for simulating {\em adaptive queries} to certain complexity classes with the power of postselection.

This paper provides some interesting results toward resolving Question~\ref{ques:query-ques}.

\subsection{Our results}

Despite that we are not able to give a complete answer to Question~\ref{ques:query-ques}. We provide some interesting lower bounds showing that certain functions' adaptive versions are hard for these postselection classes.

Formally, we prove the following two theorems.

\begin{theo}[Quantum Case]\label{theo:ada-postbqp}
	For a family of partial function $\mathbf{f}$, $\mathsf{Ada}_{\mathbf{f}} \not\in \PostBQP^{\dt}(\PP^{\dt})$ if $\mathbf{f} \not\in \SBQP^{\dt} \cap \coSBQP^{\dt}$.
\end{theo}

\begin{theo}[Classical Case]\label{theo:ada-postbpp}
	For a family of partial function $\mathbf{f}$, $\mathsf{Ada}_{\mathbf{f}} \not\in \PostBPP^{\dt}$ if $\mathbf{f} \not\in \SBP^{\dt} \cap \coSBP^{\dt}$.
\end{theo}

Roughly speaking, $\textsf{SBP}$ is a relaxation of $\textsf{BPP}$, it is the set of languages $L$ such that there exists a $\textsf{BPP}$ machine $M$, which accepts $x$ with probability $\ge 2\alpha$ if $x \in L$; and with probability $\le \alpha$ if $x \not\in L$ for a positive real number $\alpha$. And $\textsf{SBQP}$ is the quantum analogue of $\textsf{SBP}$, where you are allowed to use a polynomial time quantum algorithm instead.\footnote{For the formal definitions of $\textsf{SBP}$, $\textsf{PostBPP}$, $\textsf{PostBQP}$, $\textsf{SBQP}$ and their equivalents in query complexity, see the preliminaries.}

Our theorems show that, for a partial function $f$, if there is no efficient classical (quantum) algorithm which accepts all the $1$-inputs with a slightly better chance than all the $0$-inputs, then there is no efficient $\textsf{PostBPP}$ ($\textsf{PostBQP}$) algorithm that can answer adaptive queries to $f$.

In fact, we prove the following two quantitatively tighter theorems, from which Theorem~\ref{theo:ada-postbqp} and Theorem~\ref{theo:ada-postbpp} follows easily.

\begin{theo} \label{theo:hard-adapt-postbqp}
	Let $f$ be a partial function and $T$ be a non-negative integer. Suppose $\widehat{\mathrm{deg}}_{+}(f) > T$ or $\widehat{\mathrm{deg}}_{-}(f) > T$, then we have
	$$
	\PP^{\dt}(\mathsf{Ada}_{f,d}) > \min(T/4,2^{d-1}).\footnote{ $\widehat{\mathrm{deg}}_{+}$ ({\em one-sided low-weight approximate degree}, cf. Definition~\ref{defi:low-weight}) is equivalent to $\SBQP^{\dt}$, and $\PP^{\dt}$ is equivalent to $\PostBQP^{\dt}$, see Corollary~\ref{cor:eq-SBQP-AZPP}, Corollary~\ref{cor:eq-PostBQP-PP} and Theorem~\ref{theo:eq-AZPP-mdega}. We state it in this form for simplicity.}
	$$
\end{theo}

\begin{theo} \label{theo:hard-adapt-postbpp}
	Let $f:D \to \{0,1\}$ with $D \subseteq \{0,1\}^M$ be a partial function and $d$ be a non-negative integer. Suppose $\SBP^{\dt}(f) > T$ or $\coSBP^{\dt}(f) > T$, then we have
	$$
	\PostBPP^{\dt}(\mathsf{Ada}_{f,d}) > \min(T/5,(2^{d}-1)/5).
	$$
\end{theo}

\subsection{Applications in oracle separations}

Our results have several applications in oracle separations.
\begin{itemize}
	\item A new proof for $\textsf{P}^{\textsf{NP}^{\mathcal{O}}} \not\subset \textsf{PP}^{\mathcal{O}}$:

	We prove that $\SBQP^{\dt}(f)$ is indeed equivalent to {\em one-sided low-weight approximate degree}, denoted by $\widehat{\mathrm{deg}}_{+}(f)$ (cf. Definition~\ref{defi:low-weight}), which is lower bounded by one-sided approximate degree $\mathrm{deg}_{+}(f)$ (cf. Definition~\ref{defi:deg-approx}).

	Using the fact that $\mathrm{deg}_{+}(\mathsf{AND}_n) \ge \Omega(\sqrt{n})$, Theorem~\ref{theo:ada-postbqp} implies that $\mathsf{Ada}_{\mathbf{\mathsf{AND}}} \not\subset \PP^{\dt}$, yielding a simpler proof for the classical oracle separation between $\textsf{P}^{\textsf{NP}}$ and $\textsf{PP}$ in \cite{beigel1994perceptrons}.

	Our proof is arguably simpler and more elegant. Also, unlike the seemingly artificial problem $\textsf{ODD-MAX-BIT}$\footnote{Given a binary input $x$, it asks whether the rightest $1$ in $x$ is in an odd position.} in \cite{beigel1994perceptrons}, $\mathsf{Ada}_{\mathbf{\mathsf{AND}}}$ looks like a more natural hard problem in $\textsf{P}^{\textsf{NP}}$.
	\item The new oracle separation $\textsf{P}^{\textsf{SZK}^{\mathcal{O}}} \not\subset \textsf{PP}^{\mathcal{O}}:$

    Since the {\em Permutation Testing Problem}, denoted by $\mathsf{PTP}_n$ (see Problem~\ref{prob:PTP} for a formal definition), satisfies $\mathrm{deg}_{+}(\mathsf{PTP}_n) \ge \Omega(n^{1/3})$ and has a $\log(n)$-time $\textsf{SZK}$ protocol. Theorem~\ref{theo:ada-postbqp} implies that $\mathsf{Ada}_{\mathsf{PTP}} \not\subset \PP^{\dt}$, which in turn shows an oracle separation between $\textsf{P}^{\textsf{SZK}}$ and $\textsf{PP}$.

    It has been an open problem~\cite{aaronson2012impossibility} that whether there exists an oracle separation between $\textsf{SZK}$ and $\textsf{PP}$, our result is pretty close to an affirmative answer to that.\footnote{Partially inspired by this work, an oracle separation between $\textsf{SZK}$ and $\textsf{PP}$ (in fact, $\mathsf{UPP}$) has been constructed in a very recent work of Bouland, Chen, Holden, Thaler and Vasudevan~\cite{bouland2016szk}, thus resolved this open problem.}

    Also, note that $\textsf{P}^{\textsf{SZK}} \subseteq \textsf{P}^{\textsf{AM} \cap \textsf{coAM}} = \textsf{AM} \cap \textsf{coAM}$,  so our result improves on the oracle separation between $\textsf{AM} \cap \textsf{coAM}$ and $\textsf{PP}$ by Vereschchagin~\cite{vereschchagin1992power}.
\end{itemize}

\subsection{Applications in hardness amplification for polynomial approximation}

Our construction also leads to a hardness amplification theorem for polynomial approximation. In order to state our result, we need to introduce the definition of two approximate degrees first.

\begin{defi}\label{defi:deg-approx}
	The $\epsilon$-approximate degree of a partial function of $f: D \to \{0,1\}$, denoted as $\widetilde{\mathrm{deg}}_\epsilon(f)$, is the least degree of a real polynomial $p$ such that $|p(x)-f(x)| \le \epsilon$ when $x \in D$, and $|p(x)| \le 1+\epsilon$ when $x\not\in D$.

	We say a polynomial $p$	one-sided $\epsilon$-approximates a partial Boolean function $f$, if $p(x) \in [0,\epsilon]$ when $f(x) = 0$, and $p(x) \ge 1$ when $f(x) = 1$.\footnote{Our definition of one-sided approximation is slightly different from the standard one~\cite{sherstov2014breaking,bun2015dual,sherstov2015power}, but it greatly simplifies several discussions in our paper, and they are clearly equivalent up to a linear transformation in $\epsilon$.} Then the one-sided $\epsilon$-approximate degree of a partial function $f$, denoted by $\mathrm{deg}_{+}^{\epsilon}(f)$, is the minimum degree of a polynomial one-sided $\epsilon$-approximating $f$.
\end{defi}

Now we are in a position to state our amplification theorem.

\begin{theo}\label{theo:ampl}
	Let $f$ be a partial function such that $\mathrm{deg}_{+}^{2/3}(f) > T$ and $d$ be a positive integer, we have $\widetilde{\mathrm{deg}}_{\epsilon}(\mathsf{Ada}_{f,d}) > T$ for $\epsilon = 0.5-2^{-2^d+1}$.
\end{theo}

\newcommand{\mathsf{AdaQ}}{\mathsf{AdaQ}}

That is, given a function with high one-sided approximate degree for an error constant bounded away from $1$, it can be transformed to a function with high approximate degree even for $\epsilon$ {\em doubly exponentially} close to $1/2$ in $d$.\footnote{Which is {\em single exponential} in the input length of the {\em amplifier} $\mathsf{AdaQ}$, see the discussion below.}

\paragraph*{Comparison with previous amplification results}

There have been a lot of research interest in hardness amplification for polynomial approximation, many amplification results are achieved through {\em function composition}~\cite{bun2015hardness,sherstov2014breaking,thaler2014lower}. We use $f \circ g$ to denote the block composition of $f$ and $g$, i.e. $f(g,g,\dotsc,g)$.

Our result can also be viewed as one of them. Let $\mathsf{AdaQ}_{d} := \mathsf{Ada}_{\mathsf{id},d}$, where $\mathsf{id}$ is just the identity function from $\{0,1\}$ to $\{0,1\}$. Then we can see that in fact $\mathsf{Ada}_{f,d}$ is equivalent to $\mathsf{AdaQ}_{d} \circ f$. Let $n = 2^{d+1} - 1$, which is the input length of $\mathsf{AdaQ}_{d}$.

However, all the previous amplification results are achieved by letting the {\em amplifier} $f$ to be a {\em hard} function. We list all these results for an easy comparison.

\begin{itemize}
	\item In the work of Bun and Tahler~\cite{bun2015hardness}, they showed that for a function $g$ such that $\mathrm{deg}_{+}(g) > T$, $\widetilde{\mathrm{deg}}_\epsilon(\mathsf{OR}_n \circ g) > T$ for $\epsilon = 1/2 - 2^{-\Omega(n)}$. This is further improved by Sherstov~\cite{sherstov2014breaking} to that $\mathrm{deg}_{\pm}(\mathsf{OR}_n \circ g) = \Omega(\min(n,T))$. Here, the amplifier $\mathsf{OR}_n$ is a hard function in the sense that $\mathrm{deg}_{+}(\mathsf{OR}_n) \ge \Omega(\sqrt{n})$~\cite{nisan1994degree}.
	\item In~\cite{thaler2014lower}, Thaler showed that for a function $g$ such that $\mathrm{deg}_{+}(g) > T$, $\widetilde{\mathrm{deg}}_\epsilon(\textsf{ODD-MAX-BIT}_n \newline\circ g) > T$ for $\epsilon = 1/2 - 2^{-\Omega(n)}$.\footnote{This construction is further improved in a very recent work~\cite{bun2016approximate} by Bun and Thaler, with a more sophisticated construction which does not follow the composition paradigm.} In this case, the amplifier $\textsf{ODD-MAX-BIT}_n$ is even harder in the sense that it has a $\PP^{\dt}$ query complexity of $\Omega(\sqrt[3]{n})$~\cite{beigel1994perceptrons}.
	\item Moreover, it is easy to see that the {\em randomized query complexity} of both $\mathsf{OR}_n$ and $\textsf{ODD-MAX-BIT}_n$ is the maximum possible $\Omega(n)$.
\end{itemize}

In contrast, our amplifier $\mathsf{AdaQ}$, is {\em extremely} simple\textemdash it has a {\em deterministic query complexity} of $O(\log n)$!\footnote{A simple $O(\log n)$-query algorithm just follows from the definition.}

This is a rather surprising feature of our result. That means $\mathsf{AdaQ}$ also has an {\em exact degree} of $O(\log n)$.
Intuitively, composing with such a simple and innocent function seems would not affect the hardness of the resulting function. Our result severely contradicts this intuition. But from the view point of Theorem~\ref{theo:ada-postbqp}, composing with $\mathsf{AdaQ}$ indeed ``adaptivize'' the function, makes it hard for \textsf{PostBQP}\ algorithms, which is in turn closely connected to $\textsf{PP}$ algorithms and therefore polynomial approximate degree. So this result is arguably natural under that perspective, which illustrates a recurring theme in TCS: a new perspective can lead to some unexpected results.

\subsection{Paper organization}

In Section~\ref{sec:pre} we introduce some preliminaries, due to the space constraints, some of the formal definitions of those partial function classes in query complexity can be found in the appendix.
We prove Theorem~\ref{theo:ada-postbqp} and Theorem~\ref{theo:hard-adapt-postbqp} in Section~\ref{sec:quantum}, and defer the proof for Theorem~\ref{theo:ada-postbpp} and Theorem~\ref{theo:hard-adapt-postbpp} to the appendix. Theorem~\ref{theo:ampl} is proved in Section~\ref{sec:amply}. And we provide formal proofs for the two oracle separation results in the appendix.
\section{Formal proofs for the oracle separations}\label{sec:oracle}

\paragraph*{$\textsf{P}^{\textsf{NP}^{\mathcal{O}}} \not\subset \textsf{PP}^{\mathcal{O}}$}
We begin with a famous lower bound on $\mathrm{deg}_{+}(\mathsf{AND}_n)$ by Nisan and Szegedy.

\begin{theo}[\cite{nisan1994degree}]
$\mathrm{deg}_{+}(\mathsf{AND}_n) \ge \Omega(\sqrt{n})$.
\end{theo}

Then we consider the problem $\mathsf{AdaAND}_n := \mathsf{Ada}_{\mathsf{AND}_n,\log_2 n}$.

By Theorem~\ref{theo:hard-adapt-postbqp}, we have

$$
\PP^{\dt}(\mathsf{AdaAND}_n) \ge \Omega(\sqrt{n}).
$$

On the other hand, there is a simple $\operatorname*{polylog}(n)$-time $\textsf{P}^{\textsf{NP}}$ algorithm for $\mathsf{AdaAND}$. By a standard diagonalization argument, we have the following corollary.

\begin{cor}
There exists an oracle $\mathcal{O}$ such that $\textsf{P}^{\textsf{NP}^{\mathcal{O}}} \not\subset \textsf{PP}^{\mathcal{O}}$.
\end{cor}

\paragraph*{$\textsf{P}^{\textsf{SZK}^{\mathcal{O}}} \not\subset \textsf{PP}^{\mathcal{O}}$}
In order to establish the oracle separation between $\textsf{P}^{\textsf{SZK}}$ and $\textsf{PP}$, we need the following results in \cite{aaronson2012impossibility}.

\begin{theo}[Essentially Theorem~8 in~\cite{aaronson2012impossibility}]\label{theo:PTP-lowb}
	$\mathrm{deg}_{+}(\mathsf{PTP}_n) \ge \Omega(n^{1/3})$.
\end{theo}

\begin{prop}[Proposition 2 in~\cite{aaronson2012impossibility}]\label{theo:PTP-easy}
	$\mathsf{PTP}_n$ has an $O(\log n)$ time $\textsf{SZK}$ protocol.
\end{prop}

Then for the problem $\mathsf{AdaPTP}_n := \mathsf{Ada}_{\mathsf{PTP}_n,\log_2 n}$, by Theorem~\ref{theo:PTP-lowb} and Theorem~\ref{theo:ada-postbqp}, we have
$$
\PP^{\dt}(\mathsf{AdaPTP}_n) \ge \Omega(n^{1/3}).
$$

By Proposition~\ref{theo:PTP-easy}, we can see $\mathsf{AdaPTP}$ admits a $\operatorname*{polylog}(n)$-time $\textsf{P}^{\textsf{SZK}}$ algorithm, hence again by a standard diagonalization argument, we have the following corollary.

\begin{cor}
	There exists an oracle $\mathcal{O}$ such that $\textsf{P}^{\textsf{SZK}^{\mathcal{O}}} \not\subset \textsf{PP}^{\mathcal{O}}$.
\end{cor}
\section{Preliminaries}\label{sec:pre}

\subsection{Decision trees and quantum query algorithms}

A (randomized) decision tree is the analogue of a deterministic (randomized) algorithm in the query complexity world, and a quantum query algorithm is the analogue of a quantum algorithm. See \cite{buhrman2002complexity} for a nice survey on query complexity.

Let $\mathcal{T}$ be a randomized decision tree, we use $\mathcal{C}(\mathcal{T})$ to denote the maximum number of queries incurred by $\mathcal{T}$ in the worst case\footnote{i.e. the maximum height of a decision tree in the support of $\mathcal{T}$}. Let $\mathcal{Q}$ be a quantum query algorithm, we use $\mathcal{C}(\mathcal{Q})$ to denote the number of queries taken by $\mathcal{Q}$.

We assume a randomized decision tree $\mathcal{T}$ (or a quantum query algorithm $\mathcal{Q}$) outputs a result in $\{0,1\}$, and we use $\mathcal{T}(x)$ ($\mathcal{Q}(x)$) to denote the (random) output of $\mathcal{T}$ ($\mathcal{Q}$) given an input $x$.

\subsection{Complexity classes and their query complexity analogues}

We assume familiarity with some standard complexity classes like \textsf{PP}. Due to space constraint, we only introduce the most relevant classes $\AzPP^{\dt}$ and $\PP^{\dt}$ here, and defer the formal definitions of the partial function complexity classes $\SBP^{\dt}$, $\SBQP^{\dt}$, $\PostBPP^{\dt}$ and $\PostBQP^{\dt}$ to the appendix.

Recall that $\mathcal{C}^{\textsf{dt}}$ is the set of the partial function family $\mathbf{f}$ with $\mathcal{C}^{\textsf{dt}}(f) = O(\operatorname*{polylog}(\mathsf{len}(f)))$ for all $f \in \mathbf{f}$, hence we only need to define $\mathcal{C}^{\textsf{dt}}(f)$ for a partial function $f$.

\paragraph*{$\PP^{\dt}$}

We first define $\PP^{\dt}(f)$.

\begin{defi}\label{defi:PPdt}
	Let $f:D \to \{0,1\}$ with $D \subseteq \{0,1\}^M$ be a partial function. Let $\mathcal{T}$ be a randomized decision tree which computes $f$ with a probability better than $1/2$. Let $\alpha$ be the maximum real number such that
	$$
	\Pr[\mathcal{T}(x) = f(x)] \ge \frac{1}{2} + \alpha
	$$
	for all $x \in D$.

	Then we define $\PP^{\dt}(\mathcal{T};f) := C(\mathcal{T}) + \log_2(1/\alpha)$, and $\PP^{\dt}(f)$ as the minimum of $\PP^{\dt}(\mathcal{T};f)$ over all $\mathcal{T}$ computing $f$ with a probability better than $1/2$.
\end{defi}

\paragraph*{$\textsf{A0PP}$ and $\AzPP^{\dt}$}
In this subsection we review the definition of $\textsf{A0PP}$, and define its analogue in query complexity. There are several equivalent definitions for $\textsf{A0PP}$, we choose the most convenient one here.

\begin{defi}
	$\textsf{A0PP}$ (defined by Vyalyi~\cite{vyalyi2003qma}) is the class of languages $L\subseteq\left\{
	0,1\right\}  ^{\ast}$\ for which there exists a $\mathsf{BPP}$\ machine $M$ and a polynomial $p$, such that for all inputs $x$:
	\begin{enumerate}
		\item[(i)] $x\in L\Longrightarrow\Pr\left[  M\left(  x\right)  \text{ accepts}\right]\geq \frac{1}{2} + 2^{-p(|x|)}$.

		\item[(ii)] $x\notin L\Longrightarrow\Pr\left[  M\left(  x\right)  \text{
			accepts}\right]  \in \left[\frac{1}{2}, \frac{1}{2} + 2^{-p(|x|)-1} \right]$.
	\end{enumerate}
\end{defi}

\begin{defi}\label{defi:AzPPdt}

	Let $f:D \to \{0,1\}$ with $D \subseteq \{0,1\}^M$ be a partial function. We say a randomized decision tree $\mathcal{T}$ $\textsf{A0PP}$-computes $f$ if there is a real number $\alpha > 0$ such that
	\begin{itemize}
		\item $\Pr[\mathcal{T}(x)=1] \ge 1/2 + 2\alpha$ when $f(x) = 1$.
		\item $\Pr[\mathcal{T}(x)=1] \in [1/2, 1/2 + \alpha]$ when $f(x) = 0$.
	\end{itemize}
	Fix a $\mathcal{T}$ $\textsf{A0PP}$-computing $f$, let $\alpha$ be the maximum real number satisfying above conditions. Then we define $\AzPP^{\dt}(\mathcal{T};f) = C(\mathcal{T}) + \log_2(1/\alpha)$ for $\mathcal{T}$ $\textsf{A0PP}$-computing $f$ and $\AzPP^{\dt}(f)$ as the minimum of $\AzPP^{\dt}(\mathcal{T};f)$ over all $\mathcal{T}$ $\AzPP^{\dt}$-computing $f$. And we simply let $\coAzPP^{\dt}(f) := \AzPP^{\dt}(\neg f)$.
\end{defi}

\paragraph*{Two relativized facts}

We also introduce two important relativized results here.
In \cite{aaronson2005quantum}, Aaronson showed that $\textsf{PostBQP}$ is indeed $\textsf{PP}$ in disguise.

\begin{theo}[\cite{aaronson2005quantum}]
	$\textsf{PostBQP} = \textsf{PP}$.
\end{theo}

And in~\cite{kuperberg2009hard}, Kuperberg showed that $\textsf{SBQP}$ is in fact equal to $\textsf{A0PP}$.

\begin{theo}[\cite{kuperberg2009hard}]
	$\textsf{SBQP} = \textsf{A0PP}$.
\end{theo}

These two theorems relativize, hence we have the following corollaries.

\begin{cor}\label{cor:eq-SBQP-AZPP}
	$\SBQP^{\dt} = \AzPP^{\dt}$.
\end{cor}

\begin{cor}\label{cor:eq-PostBQP-PP}
	$\PostBQP^{\dt} = \PP^{\dt}.$
\end{cor}
\subsection{Low-weighted one-sided approximate degree}

In this subsection, we introduce a new notion of one-sided approximate degree, which is closely connected to $\AzPP^{\dt}(f)$.

\begin{defi} \label{defi:low-weight}
Write a polynomial $p(x) := \sum_{i=1}^{m} a_i \cdot M_i(x)$ as a sum of monomials, we define $\mathsf{weight}(p) := \sum_{i=1}^{m} |a_i|$. The one-sided low-weight $\epsilon$-approximate degree of a partial function $f$ denoted by $\widehat{\mathrm{deg}}_{+}^{\epsilon}(f)$, is defined by
$$
\widehat{\mathrm{deg}}_{+}^{\epsilon}(f) := \min_{p} \max \{\mathrm{deg}(p),\log_2(\mathsf{weight}(p)) \},
$$
where $p$ goes over all polynomials which one-sided $\epsilon$-approximates $f$.\footnote{Recall that a polynomial $p$ one-sided $\epsilon$-approximates a partial Boolean function $f$, if $p(x) \in [0,\epsilon]$ when $f(x) = 0$, and $p(x) \ge 1$ when $f(x) = 1$ as in Definition~\ref{defi:deg-approx}.}

We simply let $\widehat{\mathrm{deg}}_{-}^{\epsilon}(f) := \widehat{\mathrm{deg}}_{+}^{\epsilon}(\neg f)$. We also define $\widehat{\mathrm{deg}}_{+}(f)$ as $\widehat{\mathrm{deg}}_{+}^{1/2}(f)$. $\widehat{\mathrm{deg}}_{-}$ is defined similarly.
\end{defi}

Clearly $\widehat{\mathrm{deg}}_{+}^{\epsilon}(f) \ge \mathrm{deg}_{+}^{\epsilon}(f)$. And the choice of constant $1/2$ is arbitrary, as we can reduce the approximation error by the following lemma.

\begin{lem}\label{lm:amply}
	For any $0 < \epsilon_1 < \epsilon_2 < 1$, $\widehat{\mathrm{deg}}_{+}^{\epsilon_1}(f) \le \left\lceil \frac{ \ln \epsilon_1^{-1}}{ \ln \epsilon_2^{-1} } \right\rceil \cdot \widehat{\mathrm{deg}}_{+}^{\epsilon_2}(f)$.
\end{lem}
\begin{proof}
	We can just take the $\left\lceil \frac{ \ln \epsilon_1^{-1}}{ \ln \epsilon_2^{-1} } \right\rceil^{th}$ power of the polynomial corresponding to $\widehat{\mathrm{deg}}_{+}^{\epsilon_2}(f)$.
\end{proof}

We show that $\widehat{\mathrm{deg}}_{+}(f)$ is in fact equivalent to $\AzPP^{\dt}(f)$ up to a constant factor.

\begin{theo}\label{theo:eq-AZPP-mdega}
Let $f$ be a partial function, then
$$
\widehat{\mathrm{deg}}_{+}(f) \le 2 \cdot \AzPP^{\dt}(f) \text{ and } \AzPP^{\dt}(f) \le 2 \cdot \widehat{\mathrm{deg}}_{+}(f) + 2.
$$
\end{theo}

The proof is based on a simple transformation between a decision tree and the polynomial representing it, we defer the details to the appendix.

And the following corollary follows from the definitions.

\begin{cor}\label{cor:mdegs-bound}
	Let $f$ be a partial function, then
	$$
	\widehat{\mathrm{deg}}_{-}(f) \le 2 \cdot \coAzPP^{\dt}(f)  \text{ and } \coAzPP^{\dt}(f) \le 2 \cdot \widehat{\mathrm{deg}}_{-}(f) + 2.
	$$
\end{cor}

\subsection{The permutation testing problem}

Finally, we introduce the permutation testing problem.

\begin{problem}[Permutation Testing Problem or PTP]\label{prob:PTP} Given black-box access to a function
		$f:\left[  n\right]  \rightarrow\left[  n\right]  $, and promised that either

		\begin{enumerate}
			\item[(i)] $f$ is a permutation (i.e., is one-to-one), or

			\item[(ii)] $f$ differs from every permutation on at least $n/8$\ coordinates.
		\end{enumerate}

		The problem is to accept if (i) holds and reject if (ii) holds.

		Assume $n$ is a power of $2$, we use $\mathsf{PTP}_n$ to denote the Permutation Testing Problem on functions from $[n] \to [n]$. $\mathsf{PTP}_n$ can be viewed as a partial function $D \to \{0,1\}$ with $D \subseteq \{0,1\}^{n \cdot \log_2 n}$.
\end{problem}
\section{Proof for the quantum case}\label{sec:quantum}

In this section we prove Theorem~\ref{theo:ada-postbqp}.

Let $f:D \to \{0,1\}$ with $D \subseteq \{0,1\}^M$ be a partial function, we say a polynomial $p$ on $M$ variables {\em computes} $f$, if $p(x) \ge 1$ whenever $f(x)=1$, and $p(x) \le -1$ whenever $f(x)=0$.

\subsection{Existence of the hard distributions}
In this subsection we show that if $\widehat{\mathrm{deg}}_{+}(f)$ is large, there must exist some input distributions witness this fact in a certain sense.

\begin{lem}\label{lm:single-dist-exist-mdega}
Let $f$ be a partial function and $T$ be a non-negative integer. For convenience, we say a polynomial $p$ is {\em valid}, if it is of degree at most $T$, and satisfies $\mathsf{weight}(p) \le 2^{T}$.

If $\widehat{\mathrm{deg}}_{+}^{2/3}(f) > T$, there exist two distributions $\mathcal{D}_0$ and $\mathcal{D}_1$ supported on $f^{-1}(0)$ and $f^{-1}(1)$ respectively, such that
$$
- p(\mathcal{D}_0) > 2 \cdot p(\mathcal{D}_1),
$$
where $p(\mathcal{D}) = \mathbb{E}_{x \sim \mathcal{D}}[p(x)]$, for all valid polynomial $p$ computing $f$.
\end{lem}

In order to establish the above lemma, we need the following simple lemma.

\begin{lem}\label{lm:help-1}
For any valid polynomial $p$ computing $f$, if $\widehat{\mathrm{deg}}_{+}^{2/3}(f) > T$, then there exist $x \in f^{-1}(0)$ and $y \in f^{-1}(1)$ such that $-p(x) > 2 \cdot p(y)$.
\end{lem}

The proof is based on a simple calculation, the details can be found in the appendix.

Then we prove Lemma~\ref{lm:single-dist-exist-mdega}.

\begin{proofof}{Lemma~\ref{lm:single-dist-exist-mdega}}
By Lemma~\ref{lm:help-1}, we have
$$
\min_{\text{$p$}} \max_{(x,y) \in f^0 \times f^1} -p(x) - 2 \cdot p(y) > 0,
$$
where $p$ is a valid polynomial which computes $f$, $f^0 := f^{-1}(0)$ and $f^1 := f^{-1}(1)$. By the minimax theorem, and note that all the valid polynomials form a {\em compact convex set}, there exists a distribution $\mathcal{D}_{xy}$ on $f^0 \times f^1$ such that for any valid polynomial $p$ computing $f$, we have
$$
\mathbb{E}_{(x,y) \sim \mathcal{D}_{xy}}[-p(x)-2 \cdot p(y)] > 0.
$$
Then we simply let $\mathcal{D}_0$ ($\mathcal{D}_1$) be the marginal distribution of $\mathcal{D}_{xy}$ on $f^0$ ($f^1$), which completes the proof.
\end{proofof}

And the following corollary follows by the definition of $\widehat{\mathrm{deg}}_{-}$.

\begin{cor}\label{cor:single-dist-exist-mdegs}
	Let $f$ be a partial function and $T$ be a non-negative integer, if $\widehat{\mathrm{deg}}_{-}^{2/3}(f) > T$, then there exist two distributions $\mathcal{D}_0$ and $\mathcal{D}_1$ supported on $f^{-1}(0)$ and $f^{-1}(1)$ respectively, such that for all valid polynomial $p$ computing $f$,
	$$
	p(\mathcal{D}_1) > -2 \cdot p(\mathcal{D}_0).
	$$
\end{cor}

\subsection{Proof for Theorem~\ref{theo:ada-postbqp} and Theorem~\ref{theo:hard-adapt-postbqp}}

We first show Theorem~\ref{theo:hard-adapt-postbqp} implies Theorem~\ref{theo:ada-postbqp}.

\begin{proofof}{Theorem~\ref{theo:ada-postbqp}}
	Suppose $\mathbf{f} \not\in \SBQP^{\dt}$, the case that $\mathbf{f} \not\in \coSBQP^{\dt}$ is similar.

	By Corollary~\ref{cor:eq-SBQP-AZPP} and Theorem~\ref{theo:eq-AZPP-mdega}, there exists a sequence of function $\{f_i\}_{i=1}^{\infty} \subseteq \mathbf{f}$ such that $\widehat{\mathrm{deg}}_{+}(f_i) > \log(\mathsf{len}(f_i))^{i}$. Then we consider the partial function sequence $\{ \mathsf{Ada}_{f_i,\lceil\log(\mathsf{len}(f_i)) \rceil} \}_{i=1}^{\infty} \subseteq \mathsf{Ada}_{\mathbf{f}}$.

	By Theorem~\ref{theo:hard-adapt-postbqp}, we have
	$$
	\PP^{\dt}(\mathsf{Ada}_{f_i,\lceil\log(\mathsf{len}(f_i)) \rceil}) > \min(\log(\mathsf{len}(f_i))^{i}/4,\mathsf{len}(f_i)/2).
	$$
	Note that $\mathsf{len}(\mathsf{Ada}_{f_i,\lceil\log(\mathsf{len}(f_i)) \rceil}) \le 2 \cdot \mathsf{len}(f_i)^2$, we can see $\mathsf{Ada}_{\mathbf{f}} \notin \PP^{\dt}$ due to the above partial function sequence.
\end{proofof}

Now, we are going to prove Theorem~\ref{theo:hard-adapt-postbqp}. We begin by introducing some consequences of a function having low $\PP^{\dt}$ complexity.

\begin{lem}\label{lm:pps-cons}
	Let $f$ be a partial function, $T$ be a positive integer. Suppose $\PP^{\dt}(f) \le T$, then there exists a degree $T$-polynomial $p$ computing $f$ and satisfying $\mathsf{weight}(p) \le 2^{2T}$.
\end{lem}

The proof is based on a direct analysis of the polynomial representing the decision tree for $\PP^{\dt}(f)$, we defer the details to the appendix.

Our proof relies on the following two key lemmas.

\begin{lem}\label{lm:dist-exist-mdega}
	Let $f$ be a partial function with $\widehat{\mathrm{deg}}_{+}^{2/3}(f) > T$. Then for each integer $d$, there exist two distributions $\mathcal{D}_1^d$ and $\mathcal{D}_0^d$ supported on $\mathsf{Ada}_{f,d}^{-1}(1)$ and $\mathsf{Ada}_{f,d}^{-1}(0)$ respectively, such that $- p(\mathcal{D}_0) > 2^{2^d} \cdot p(\mathcal{D}_1)$ for any degree-$T$ polynomial $p$ computing $\mathsf{Ada}_{f,d}$ and satisfying $\mathsf{weight}(p) \le 2^{T}$.
\end{lem}

\begin{lem}\label{lm:dist-exist-mdegs}
	Let $f$ be a partial function with $\widehat{\mathrm{deg}}_{-}^{2/3}(f) > T$. Then for each integer $d$, there exist two distributions $\mathcal{D}_1^d$ and $\mathcal{D}_0^d$ supported on $\mathsf{Ada}_{f,d}^{-1}(1)$ and $\mathsf{Ada}_{f,d}^{-1}(0)$ respectively, such that $p(\mathcal{D}_1) > -2^{2^d} \cdot p(\mathcal{D}_0)$ for any degree-$T$ polynomial $p$ computing $\mathsf{Ada}_{f,d}$ and satisfying $\mathsf{weight}(p) \le 2^{T}$.
\end{lem}

We first show these two lemmas imply Theorem~\ref{theo:hard-adapt-postbqp} in a straightforward way.

\begin{proofof}{Theorem~\ref{theo:hard-adapt-postbqp}}
We prove the case when $\widehat{\mathrm{deg}}_{+}(f) > T$ first.

Otherwise, suppose $\PP^{\dt}(\mathsf{Ada}_{f,d}) \le \min(T/4,2^{d-1})$. By Lemma~\ref{lm:pps-cons}, we have a degree-$T/4$ polynomial $p$ computing $\mathsf{Ada}_{f,d}$ with $\mathsf{weight}(p) \le \min(2^{T/2},2^{2^d})$. From Lemma~\ref{lm:amply}, $\widehat{\mathrm{deg}}_{+}(f)=\widehat{\mathrm{deg}}_{+}^{1/2}(f) \le 2 \cdot \widehat{\mathrm{deg}}_{+}^{2/3}(f)$, hence $\widehat{\mathrm{deg}}_{+}^{2/3}(f) > T/2$. Then by Lemma~\ref{lm:dist-exist-mdega}, there exist two distributions $\mathcal{D}_1^d$ and $\mathcal{D}_0^d$ supported on $\mathsf{Ada}_{f,d}^{-1}(1)$ and $\mathsf{Ada}_{f,d}^{-1}(0)$ respectively, such that $- p(\mathcal{D}_0) > 2^{2^d} \cdot p(\mathcal{D}_1)$ as $p$ is of degree at most $T/4$ and satisfies $\mathsf{weight}(p) \le 2^{T/2}$.

But this means that $-p(\mathcal{D}_0) > 2^{2^d}$, which implies there exists an $x$ such that $p(x) < -2^{2^d}$, therefore $\mathsf{weight}(p) > 2^{2^d}$, contradiction.

The case when $\widehat{\mathrm{deg}}_{-}(f) > T$ follows exactly in the same way by using Lemma~\ref{lm:dist-exist-mdegs} instead of Lemma~\ref{lm:dist-exist-mdega}.
\end{proofof}

\newcommand{f_{\PTP}}{f_{\mathsf{PTP}}}

\subsection{Proof for Lemma~\ref{lm:dist-exist-mdega}}
Finally we prove Lemma~\ref{lm:dist-exist-mdega}. The proof for Lemma~\ref{lm:dist-exist-mdegs} is completely symmetric using Corollary~\ref{cor:single-dist-exist-mdegs} instead of Lemma~\ref{lm:single-dist-exist-mdega}.
\begin{proofof}{Lemma~\ref{lm:dist-exist-mdega}}
	Recall that a polynomial $p$ is valid, if it is of degree at most $T$, and satisfies $\mathsf{weight}(p) \le 2^{T}$. Let $f_d := \mathsf{Ada}_{f,d}$ and $D_d$ be the domain of $f_d$. We are going to construct these distributions $\mathcal{D}_0^{d}$'s and $\mathcal{D}_1^{d}$'s by an elegant induction.

	{\bf Construction of $\mathcal{D}_0$ and $\mathcal{D}_1$ from Lemma~\ref{lm:single-dist-exist-mdega}.} By Lemma~\ref{lm:single-dist-exist-mdega} there exist two distributions $\mathcal{D}_0$ and $\mathcal{D}_1$ supported on $f^{-1}(0)$ and $f^{-1}(1)$ respectively, such that $ - p(\mathcal{D}_0) > 2 \cdot p(\mathcal{D}_1) $ for all valid polynomial $p$ computing $f$.

	{\bf The base case: construction of $\mathcal{D}_0^0$ and $\mathcal{D}_1^0$.}
	For the base case $d=0$, as $f_0$ is just $f$, we simply set $\mathcal{D}_0^0 = \mathcal{D}_0$ and $\mathcal{D}_1^0 = \mathcal{D}_1$. Then for all valid polynomial $p$ computing $f_0$, we have $- p(\mathcal{D}_0^0) > 2 \cdot p(\mathcal{D}_1^0) = 2^{2^0} \cdot p(\mathcal{D}_1^0)$.

	{\bf Construction of $\mathcal{D}_0^{d}$ and $\mathcal{D}_1^{d}$ for $d > 0$.}
	When $d>0$, suppose that we have already constructed the required distributions $\mathcal{D}_0^{d-1}$ and $\mathcal{D}_1^{d-1}$ for $f_{d-1}$. Decompose the input to $f_d$ as $(w,x,y) \in D \times D_{d-1} \times D_{d-1}$ as in the definition, we claim that
	$$\mathcal{D}_{0}^d = (\ddd{0}{0}{0})\footnote{($\ddd{0}{0}{0})$ is interpreted as the product distribution $\mathcal{D}_0 \times \mathcal{D}_{0}^{d-1} \times \mathcal{D}_0^{d-1}$ on $ D \times D_{d-1} \times D_{d-1}$.} \text{  and  }  \mathcal{D}_{1}^d = (\ddd{1}{1}{1})$$ satisfy our conditions.

	{\bf Analysis of $\mathcal{D}_0^{d}$ and $\mathcal{D}_1^{d}$.}
	Note that $D_{i}^d$ is supported on $f_d^{-1}(i)$ for $i \in \{0,1\}$ from the definition. Let $p(w,x,y)$ be a valid polynomial computing $f_d$. We set
	$$p(\mathcal{D}_w,\mathcal{D}_x,\mathcal{D}_y) := \mathbb{E}_{w\sim \mathcal{D}_w, x \sim \mathcal{D}_x, y\sim \mathcal{D}_y}[p(w,x,y)]$$ for simplicity, where $\mathcal{D}_w,\mathcal{D}_x,\mathcal{D}_y$ are distributions over $D,D_{d-1},D_{d-1}$ respectively.

	Then we have to verify that for all valid polynomial $p$ computing $f_d$,
	$$
	-p(\mathcal{D}_0^{d}) = -p(\ddd{0}{0}{0}) > 2^{2^d} \cdot p(\ddd{1}{1}{1}) = 2^{2^d} \cdot p(\mathcal{D}_1^d).
	$$

	We proceed by incrementally changing $(\ddd{0}{0}{0})$ into $(\ddd{1}{1}{1})$, and establish inequalities along the way.

	{\bf Step 1: $(\ddd{0}{0}{0}) \Rightarrow (\ddd{0}{1}{0})$.} By the definition, we can see that for any fixed $W \in \mathbf{support}(\mathcal{D}_0)$ and $Y \in \mathbf{support}(\mathcal{D}_0^{d-1})$, the polynomial in $x$ defined by $p_{L}(x) := p(W,x,Y)$ is a valid polynomial computing $f_{d-1}$, hence $-p_L(\mathcal{D}_0^{d-1}) > 2^{2^{d-1}} \cdot p_L(\mathcal{D}_1^{d-1})$. By linearity, we have
	$$
	-p(\ddd{0}{0}{0}) > 2^{2^{d-1}} \cdot p(\ddd{0}{1}{0}).
	$$

	{\bf Step 2: $(\ddd{0}{1}{0}) \Rightarrow (\ddd{1}{1}{0})$.} Similarly, for any fixed $X \in \mathbf{support}(\mathcal{D}_1^{d-1})$ and $Y \in \mathbf{support}(\mathcal{D}_0^{d-1})$, by the definition, we can see that the polynomial in $w$ defined by $p_M(w) := -p(w,X,Y)$ is a valid polynomial computing $f$, hence $-p_M(\mathcal{D}_0) > 2 \cdot p_M(\mathcal{D}_1)$. Again by linearity, we have
	$$
	p(\ddd{0}{1}{0}) > -2 \cdot p(\ddd{1}{1}{0}) > -p(\ddd{1}{1}{0}).
	$$

	{\bf Step 3: $(\ddd{1}{1}{0}) \Rightarrow (\ddd{1}{1}{1})$.} Finally, for any fixed $W \in \mathbf{support}(\mathcal{D}_1)$ and $X \in \mathbf{support}(\mathcal{D}_1^{d-1})$, the polynomial in $y$ defined by $p_{R}(y) := p(W,X,y)$ is a polynomial computing $f_{d-1}$, hence $-p_{R}(\mathcal{D}_0^{d-1}) > 2^{2^{d-1}} \cdot p_{R}(\mathcal{D}_1^{d-1})$. By linearity, we have
	$$
	-p(\ddd{1}{1}{0}) > 2^{2^{d-1}} \cdot p(\ddd{1}{1}{1}).
	$$

	Putting the above three inequalities together, we have
	$$
	-p(\mathcal{D}_0^{d})=-p(\ddd{0}{0}{0}) > 2^{2^d} \cdot p(\ddd{1}{1}{1}) = 2^{2^d} \cdot p(\mathcal{D}_1^d).
	$$

	This completes the proof.
\end{proofof}

\subsection{Application in hardness amplification for polynomial approximation}\label{sec:amply}

In this subsection, we slightly adapt the above proof in order to show Theorem~\ref{theo:ampl}.

For a polynomial $p$ on $n$ variables, let $\|p\|_{\infty} := \max_{x \in \{0,1\}^n} |p(x)|$. Lemma~\ref{lm:dist-exist-mdega} shows that, fix a partial function $f$ with $\widehat{\mathrm{deg}}_{+}(f) > T$, then for any polynomial computing $\mathsf{Ada}_{f,d}$ with $\mathsf{weight}(p) \le 2^{T}$, we must have $\|p\|_{\infty} > 2^{2^d}$. The restriction on $\mathsf{weight}(p)$ is essential for us to establish the connection between $\AzPP^{\dt}$ and $\widehat{\mathrm{deg}}_{+}$, but it becomes troublesome when it comes to proving a hardness amplification result.

Luckily, we can get rid of the restriction on $\mathsf{weight}(p)$ by making a stronger assumption that $\mathrm{deg}_{+}(f) > T$. Formally, we have the following analogous lemma for Lemma~\ref{lm:dist-exist-mdega}.

\begin{lem}\label{lm:www}
Let $f$ be a partial function with $\mathrm{deg}_{+}^{2/3}(f) > T$. Then for each integer $d$, there exist two distributions $\mathcal{D}_1^d$ and $\mathcal{D}_0^d$ supported on $\mathsf{Ada}_{f,d}^{-1}(1)$ and $\mathsf{Ada}_{f,d}^{-1}(0)$ respectively, such that for any degree-$T$ polynomial $p$ computing $\mathsf{Ada}_{f,d}$, $- p(\mathcal{D}_0^d) > 2^{2^d} \cdot p(\mathcal{D}_1^d)$ and consequently $\|p\|_{+\infty} > 2^{2^d}$.
\end{lem}
\begin{proof}
Using nearly the same proof for Lemma~\ref{lm:single-dist-exist-mdega}, we can show that for a partial function $f$, if $\mathrm{deg}_{+}^{2/3}(f) > T$, there exist two distributions $\mathcal{D}_0$ and $\mathcal{D}_1$ supported on $f^{-1}(0)$ and $f^{-1}(1)$ respectively, such that
$
- p(\mathcal{D}_0) > 2 \cdot p(\mathcal{D}_1)
$
for all degree-$T$ polynomial $p$ computing $f$. Then we can proceed exactly as in the proof for Lemma~\ref{lm:dist-exist-mdega} to get the desired distributions.
\end{proof}

Finally, we are ready to prove Theorem~\ref{theo:ampl}.

\begin{proofof}{Theorem~\ref{theo:ampl}}
	Let $F := \mathsf{Ada}_{f,d}$. Suppose otherwise  $\widetilde{\mathrm{deg}}_{\epsilon}(F) \le T$ for $\epsilon = 0.5-2^{-2^d+1}$. Then there exists a polynomial $p$ such that $\|p\|_{\infty} \le 1 +\epsilon$, $p(x) \le 0.5-2^{-2^d+1}$ when $F(x) = 0$, and $p(x) \ge 0.5+2^{-2^d+1}$ when $F(x) = 1$.

	Then we define polynomial $q(x) := (p(x)-0.5) \cdot 2^{2^d-1} $. It is easy to see $q(x)$ computes $F$. Also, we have $\|q\|_{\infty} \le (\|p\|_{\infty} + 0.5) \cdot 2^{2^d-1} < 2^{2^d}$, which contradicts Lemma~\ref{lm:www}, and this completes the proof.
\end{proofof}

redpajama_set_name: RedPajamaArXiv