computational complexity
Công bố khoa học tiêu biểu
* Dữ liệu chỉ mang tính chất tham khảo
Sắp xếp:
Random resolution refutations
computational complexity - Tập 28 - Trang 185-239 - 2019
We study the random resolution refutation system defined in Buss et al. (J Symb Logic 79(2):496–525, 2014). This attempts to capture the notion of a resolution refutation that may make mistakes but is correct most of the time. By proving the equivalence of several different definitions, we show that this concept is robust. On the other hand, if
......
On interactive proofs with a laconic prover
computational complexity - Tập 11 - Trang 1-53 - 2002
We continue the investigation of interactive proofs with
bounded communication, as initiated by Goldreich & Håstad (1998).
Let L be a language that has an interactive proof in which the prover
sends few (say b) bits to the verifier. We prove that the complement
$\bar L$ has a constant-round interactive proof of complexity that depends
only exponentially on b. This provides the first evidence that ......
Two tapes versus one for off-line Turing machines
computational complexity - Tập 3 - Trang 392-401 - 1993
We prove the first superlinear lower bound for a concrete, polynomial time recognizable decision problem on a Turing machine with one work tape and a two-way input tape (also called off-line 1-tape Turing machine). In particular, for off-line Turing machines we show that two tapes are better than one and that three pushdown stores are better than two (both in the deterministic and in the nondeterm......
A lower bound for randomized algebraic decision trees
computational complexity - Tập 6 - Trang 357-375 - 1996
We prove the firstnontrivial (andsuperlinear) lower bounds on the depth ofrandomized algebraic decision trees (with two-sided error) for problems being finite unions of hyperplanes and intersections of halfspaces, solving a long standing open problem. As an application, among other things, we derive, for the first time, an Ω(n
2)randomized lower bound for theKnapsack Problem, and an Ω(n logn)rando......
Unifying Known Lower Bounds via Geometric Complexity Theory
computational complexity - Tập 24 - Trang 393-475 - 2015
We show that most algebraic circuit lower bounds and relations between lower bounds naturally fit into the representation-theoretic framework suggested by geometric complexity theory (GCT), including: the partial derivatives technique (Nisan–Wigderson), the results of Razborov and Smolensky on AC
0[p], multilinear formula and circuit size lower bounds (Raz et al.), the degree bound......
Majority gates vs. general weighted threshold gates
computational complexity - Tập 2 - Trang 277-300 - 1992
In this paper we study small depth circuits that contain threshold gates (with or without weights) and parity gates. All circuits we consider are of polynomial size. We prove several results which complete the work on characterizing possible inclusions between many classes defined by small depth circuits. These results are the following:
......
Special Issue “Conference on Computational Complexity 2005” Guest Editor’s Foreword
computational complexity - Tập 15 - Trang 297-297 - 2006
The alternation hierarchy for sublogarithmic space is infinite
computational complexity - Tập 3 - Trang 207-230 - 1993
The alternation hierarchy for Turing machines with a space bound between loglog and log is infinite. That applies to all common concepts, especially a) to two-way machines with weak space-bounds, b) to two-way machines with strong space-bounds, and c) to one-way machines with weak space-bounds. In all of these cases the ∑
k
-and II
k
......
Query Complexity in Errorless Hardness Amplification
computational complexity - Tập 24 - Trang 823-850 - 2015
An errorless circuit for a Boolean function is one that outputs the correct answer or “don’t know” on each input (and never outputs the wrong answer). The goal of errorless hardness amplification is to show that if f has no size s errorless circuit that outputs “don’t know” on at most a
$${\delta}$$
......
Tổng số: 344
- 1
- 2
- 3
- 4
- 5
- 6
- 10