People who code: we want your input. Take the Survey

# Questions tagged [black-box]

The tag has no usage guidance.

11 questions
Filter by
Sorted by
Tagged with
2answers
939 views

### Approximate counting problem capturing BQP

In the black-box model, the problem of determining the output of a BPP machine $M(x,r)$ on input $x$ is the approximate counting problem of determining $E_r M(x,r)$ with additive error 1/3 (say). Is ...
1answer
6k views

### Oracle Construction for Grover's Algorithm

In Mike and Ike's "Quantum Computation and Quantum Information", Grover's algorithm is explained in great detail. However, in the book, and in all explanations I have found online for Grover's ...
3answers
417 views

### Property testing in other metrics?

There is a large literature on "property testing" -- the problem of making a small number of black box queries to a function $f\colon\{0,1\}^n \to R$ to distinguish between two cases: $f$ is a ...
2answers
624 views

### Estimating Average in Polynomial Time

Let $f \colon \lbrace 0,1 \rbrace ^ n \to (2^{-n},1]$ be a function. We want to estimate the average of $f$; that is: $\mathbb{E}[f(n)]=2^{-n}\sum_{x\in \lbrace 0,1 \rbrace ^ n}f(x)$. ...
2answers
449 views

### Exhausting Simulator of Zero-Knowledge Protocols in the Random Oracle Model

In a paper titled "On Deniability in the Common Reference String and Random Oracle Model," Rafael Pass writes: We note that when proving security according to the standard zero-knowledge definition ...
1answer
360 views

### Separation between existence of crypto primitives

I understand how one can build a crypto primitive from another crypto primitive to some extent. The constructions I know build the later primitive using the former primitive as a black box. My ...
1answer
126 views

### Is black box parallel quantum speedup ever nontrivial?

Grover's algorithm is not parallelizable, in that $p$ quantum processors searching over $n$ elements can't do better than $O(\sqrt{n/p})$ queries. Are there any oracle problems where quantum ...
2answers
516 views

### Boolean Circuit in a Black Box?

Just had this random idea... but unfortunately I'm not quite versed in complexity theory, so I thought it would be a good idea to ask it here. Let's equip a normal Turing machine with a "black box ...
0answers
148 views

### Introduction to Black-Box Separations in Cryptography

Are there any textbook-style material on black-box separations in cryptography? I tried to read the paper of Impagliazzo and Rudich but couldn't get much of it. A previous StackExchange entry gives a ...
0answers
148 views

### Are there efficient black-box constructions of sigma-protocols for SAT?

Is there a known black-box construction for the following implication? non-interactive string commitment that stretches additively by an amount which does not depend on the string being ...
1answer
81 views

### Optimalization of sum $f(x_i, x_j)$ for all $i < j$ pairs through permutation only?

$\DeclareMathOperator*{\argmin}{arg\,min}$Can something be said about the difficulty of minimizing the quantity $$g(x) = \sum_{i=1}^n\sum_{j=i+1}^n f(x_i, x_j)$$ of some string of symbols \$x \in \...