Questions tagged [black-box]
The black-box tag has no usage guidance.
13
questions
0
votes
0
answers
22
views
Why $rank(C|_V)\geq rank(C)$ for $r$-rank preserving subspace for depth 3 circuits
I was reading Deterministic Black Box PIT Testing for Generalized Depth 3 Arithmetic Circuits - Karnin and Shpilka
In the Theorem 3.4 they told $rank(C|_V)\geq rank(C)$
We have $C|_V$ which is ...
- 268
3
votes
0
answers
105
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 $...
- 131
5
votes
1
answer
145
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 ...
- 3,223
0
votes
1
answer
133
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 \...
- 690
22
votes
3
answers
8k
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 ...
- 331
2
votes
0
answers
177
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 ...
- 31
2
votes
0
answers
193
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 ...
user6973
3
votes
2
answers
572
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 ...
- 193
7
votes
1
answer
393
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 ...
- 21.4k
20
votes
2
answers
643
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)$.
...
- 16.3k
14
votes
2
answers
486
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 ...
- 16.3k
28
votes
2
answers
991
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 ...
- 7,589
20
votes
3
answers
425
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 ...
- 9,830