Zobrazeno 1 - 10
of 85
pro vyhledávání: '"van Melkebeek, Dieter"'
Given a rooted tree and a ranking of its leaves, what is the minimum number of inversions of the leaves that can be attained by ordering the tree? This variation of the problem of counting inversions in arrays originated in mathematical psychology, w
Externí odkaz:
http://arxiv.org/abs/2211.12441
We introduce a hitting set generator for Polynomial Identity Testing based on evaluations of low-degree univariate rational functions at abscissas associated with the variables. We establish an equivalence up to rescaling with a generator introduced
Externí odkaz:
http://arxiv.org/abs/2211.01062
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
We study the computational power of deciding whether a given truth-table can be described by a circuit of a given size (the Minimum Circuit Size Problem, or MCSP for short), and of the variant denoted as MKTP where circuit size is replaced by a polyn
Externí odkaz:
http://arxiv.org/abs/1710.09806
It is well-known [KST93] that the complexity of the Graph Automorphism problem is characterized by a special case of Graph Isomorphism, where the input graphs satisfy the "promise" of being rigid (that is, having no nontrivial automorphisms). In this
Externí odkaz:
http://arxiv.org/abs/1511.08189
Autor:
van Melkebeek, Dieter, Watson, Thomas
We obtain the first nontrivial time-space lower bound for quantum algorithms solving problems related to satisfiability. Our bound applies to MajSAT and MajMajSAT, which are complete problems for the first and second levels of the counting hierarchy,
Externí odkaz:
http://arxiv.org/abs/0712.2545
We describe a quantum black-box network computing the majority of N bits with zero-sided error eps using only 2N/3 + O(sqrt{N (log log N + log 1/eps)}) queries: the algorithm returns the correct answer with probability at least 1 - eps, and "I don't
Externí odkaz:
http://arxiv.org/abs/quant-ph/0109101
A set is autoreducible if it can be reduced to itself by a Turing machine that does not ask its own input to the oracle. We use autoreducibility to separate the polynomial-time hierarchy from polynomial space by showing that all Turing-complete sets
Externí odkaz:
http://arxiv.org/abs/math/9807185
A fundamental question in computational complexity asks whether probabilistic polynomial-time algorithms can be simulated deterministically with a small overhead in time (the BPP vs. P problem). A corresponding question in the realm of interactive pr
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::73166b3c33a4aef776339133968ddd32
Autor:
DELL, HOLGER1 holger.dell@gmail.com, VAN MELKEBEEK, DIETER2 dieter@cs.wisc.edu
Publikováno v:
Journal of the ACM. Jul2014, Vol. 61 Issue 4, p23-2327. 27p.
