Zobrazeno 1 - 10
of 64
pro vyhledávání: '"Theory of computation → Circuit complexity"'
A version of time-bounded Kolmogorov complexity, denoted KT, has received attention in the past several years, due to its close connection to circuit complexity and to the Minimum Circuit Size Problem MCSP. Essentially all results about the complexit
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::811370386e56ef5b730787d6b31caafb
Autor:
Shaltiel, Ronen
Publikováno v:
computational complexity. 32
Yao’s XOR lemma states that for every function f:{0,1}^k → {0,1}, if f has hardness 2/3 for P/poly (meaning that for every circuit C in P/poly, Pr[C(X) = f(X)] ≤ 2/3 on a uniform input X), then the task of computing f(X₁) ⊕ … ⊕ f(X_t) f
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::27606ccd7679185463d1a30a9b639083
https://doi.org/10.1007/s00037-023-00238-9
https://doi.org/10.1007/s00037-023-00238-9
Autor:
Kumar, Vinayak M.
We initiate the study of generalized AC0 circuits comprised of negations and arbitrary unbounded fan-in gates that only need to be constant over inputs of Hamming weight $\ge k$, which we denote GC0$(k)$. The gate set of this class includes biased LT
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0c6bc12fb125ead0db7468d3a093fb81
http://arxiv.org/abs/2304.02770
http://arxiv.org/abs/2304.02770
Autor:
Ben Lee Volk, Mrinal Kumar
Publikováno v:
ACM Transactions on Computation Theory. 14:1-14
We show that there is an equation of degree at most poly(n) for the (Zariski closure of the) set of the non-rigid matrices: that is, we show that for every large enough field 𝔽, there is a non-zero n²-variate polynomial P ∈ 𝔽[x_{1, 1}, …,
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d3e31d69b5279b4455fe8714525fa98e
https://doi.org/10.1145/3543685
https://doi.org/10.1145/3543685
Autor:
Chen, Lijie
In this paper, we obtain several new results on lower bounds and derandomization for ACC⁰ circuits (constant-depth circuits consisting of AND/OR/MOD_m gates for a fixed constant m, a frontier class in circuit complexity): 1) We prove that any polyn
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::716b45c67e6c20e1b6b4fab4a071baca
We show that a decidable promise problem has a non-interactive statistical zero-knowledge proof system if and only if it is randomly reducible via an honest polynomial-time reduction to a promise problem for Kolmogorov-random strings, with a superlog
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::d451dd83a47a4ddda71e5f4c4ebf5e8b
Autor:
Chattopadhyay, Eshan, Liao, Jyun-Jie
In a recent work, Gryaznov, Pudlák and Talebanfard (CCC '22) introduced a linear variant of read-once branching programs, with motivations from circuit and proof complexity. Such a read-once linear branching program is a branching program where each
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::2357a7597d70877415fa6c48a07df774
Rossman [In Proc. 34th Comput. Complexity Conf., 2019] introduced the notion of criticality. The criticality of a Boolean function f : {0,1}ⁿ → {0,1} is the minimum λ ≥ 1 such that for all positive integers t and all p ∈ [0,1], Pr_{ρ∼ℛ_
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::dba6984edceb0be7b2c57b2048569a28
Autor:
Cavalar, Bruno P., Oliveira, Igor C.
We establish new separations between the power of monotone and general (non-monotone) Boolean circuits: - For every k ≥ 1, there is a monotone function in AC⁰ (constant-depth poly-size circuits) that requires monotone circuits of depth Ω(log^k n
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::24e0bf070d9bd7131810af68424ce424
Following Razborov and Rudich, a "natural property" for proving a circuit lower bound satisfies three axioms: constructivity, largeness, and usefulness. In 2013, Williams proved that for any reasonable circuit class C, NEXP ⊂ C is equivalent to the
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::bd6c01905a33ef1e71a02fca25d393c0