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:
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 ......
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}$$
......
On semiring complexity of Schur polynomials
computational complexity - Tập 27 - Trang 595-616 - 2018
Semiring complexity is the version of arithmetic circuit complexity that allows only two operations: addition and multiplication. We show that semiring complexity of a Schur polynomial
$${s_\lambda(x_1,\dots,x_k)}$$
labeled by a partition
......
Asymptotic tensor rank of graph tensors: beyond matrix multiplication
computational complexity - - 2019
Random Cnf’s are Hard for the Polynomial Calculus
computational complexity - Tập 19 - Trang 501-519 - 2010
We prove linear lower bounds on the Polynomial Calculus (PC) refutation-degree of random CNF whenever the underlying field has characteristic greater than 2. Our proof follows by showing the PC refutation-degree of a unsatisfiable system of linear equations modulo 2 is equivalent to its Gaussian width, a concept defined by the late Mikhail Alekhnovich. The equivalence of refutation-degree and Gaus......
Block-symmetric polynomials correlate with parity better than symmetric
computational complexity - Tập 26 - Trang 323-364 - 2017
We show that degree-d block-symmetric polynomials in n variables modulo any odd p correlate with parity exponentially better than degree-d symmetric polynomials, if
$${n \ge cd^2 {\rm log} d}$$
and
......
Primality testing with fewer random bits
computational complexity - Tập 3 - Trang 355-367 - 1993
In the usual formulations of the Miller-Rabin and Solovay-Strassen primality testing algorithms for a numbern, the algorithm chooses “candidates”x
1,x
2, ...,x
k uniformly and independently at random from ℤ
n
, and tests if any is a “witness” to the compositeness ofn. For either algorithm, the probabilty that it errs is at most 2−k
. In this paper, we study the er......
Factorization of Polynomials Given by Arithmetic Branching Programs
computational complexity - Tập 30 - Trang 1-47 - 2021
Given a multivariate polynomial computed by an arithmetic branching
program (ABP) of size s, we show that all its factors can be
computed by arithmetic branching programs of size poly(s).
Kaltofen gave a similar result for polynomials computed by
arithmetic circuits. The previously known best upper bound for
ABP-factors was poly
......
Complexity theoretic hardness results for query learning
computational complexity - Tập 7 - Trang 19-53 - 1998
We investigate the complexity of learning for the well-studied model in which the learning algorithm may ask membership and equivalence queries. While complexity theoretic techniques have previously been used to prove hardness results in various learning models, these techniques typically are not strong enough to use when a learning algorithm may make membership queries. We develop a general tech......
Tổng số: 344
- 1
- 2
- 3
- 4
- 5
- 6
- 10