Questions tagged [black-box]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3 votes
0 answers
104 views

Outputting true with probabiltiy $P(A|B)$ given $P(B), P(B|A)$, and a function which returns true with probability $P(A)$

I have a black-box function which returns true with probability $ P(A) $, that I don't know how to calculate. I receive evidence B, and I want to create a function which returns true with probability $...
user avatar
5 votes
1 answer
140 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 ...
user avatar
0 votes
1 answer
101 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 \...
user avatar
  • 690
22 votes
2 answers
7k 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 ...
user avatar
  • 331
2 votes
0 answers
162 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 ...
user avatar
2 votes
0 answers
168 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 ...
user avatar
3 votes
2 answers
551 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 ...
user avatar
7 votes
1 answer
371 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 ...
user avatar
  • 21.3k
20 votes
2 answers
633 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)$. ...
user avatar
  • 16.3k
14 votes
2 answers
476 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 ...
user avatar
  • 16.3k
28 votes
2 answers
958 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 ...
user avatar
  • 7,469
20 votes
3 answers
421 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 ...
user avatar
  • 9,800