检索结果-内蒙古大学图书馆

Correlation Bounds Against Monotone NC¹ 30

Correlation Bounds Against Monotone NC<SUP>1</SUP>

30th Annual IEEE Conference on Computational complexity (CCC) as part of the ACM Federated Computing Research Conference (FCRC)

作者： Rossman, Benjamin Natl Inst Informat Tokyo Japan Simons Inst Theory Computat Berkeley CA USA

ISBN: (纸本)9783939897811

This paper gives the first correlation bounds under product distributions, including the uniform distribution, against the class mNC(1) of polynomial-size O(log n)-depth monotone circuits. Our main theorem, proved using the pathset complexity framework introduced in [56], shows that the average-case k-CYCLE problem (on Erdos-Renyi random graphs with an appropriate edge density) is 1/2 + 1/ poly(n) hard for mNC(1). Combining this result with O'Donnell's hardness amplification theorem [43], we obtain an explicit monotone function of n variables (in the class mSAC(1)) which is 1/2+ n(-1/2+epsilon) hard for mNC(1) under the uniform distribution for any desired constant epsilon > 0. This bound is nearly best possible, since every monotone function has agreement 1/2 + Omega( log n/root n) with some function in mNC(1) [44]. Our correlation bounds against mNC(1) extend smoothly to non-monotone NC1 circuits with a bounded number of negation gates. Using Holley's monotone coupling theorem [30], we prove the following lemma: with respect to any product distribution, if a balanced monotone function f is 1/2 + delta hard for monotone circuits of a given size and depth, then f is 1/2 + (2(t+1) - 1)delta hard for (non-monotone) circuits of the same size and depth with at most t negation gates. We thus achieve a lower bound against NC1 circuits with (1/2 - epsilon) log n negation gates, improving the previous record of 1/6 log log n [7]. Our bound on negations is "half" optimal, since [log(n + 1) e negation gates are known to be fully powerful for NC1 [3, 21].

关键词： circuit complexity average-case complexity

来源：评论

学校读者我要写书评

暂无评论

The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials 62

The Algorithmic Phase Transition of Random k-SAT for Low Deg...

引用

62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Bresler, Guy Huang, Brice MIT Dept Elect Engn & Comp Sci 77 Massachusetts Ave Cambridge MA 02139 USA

ISBN: (纸本)9781665420556

Let Phi be a uniformly random k-SAT formula with n variables and m clauses. We study the algorithmic task of finding a satisfying assignment of Phi. It is known that satisfying assignments exist with high probability up to clause density m/n = 2(k) log 2 - 1/2(log 2 + 1) + o(k)(1), while the best polynomial-time algorithm known, the Fix algorithm of Coja-Oghlan [1], finds a satisfying assignment at the much lower clause density (1 - o(k)(1))2(k) log k/k. This prompts the question: is it possible to efficiently find a satisfying assignment at higher clause densities? We prove that the class of low degree polynomial algorithms cannot find a satisfying assignment at clause density (1 + o(k)(1))kappa*2(k) log k/k for a universal constant kappa* approximate to 4.911. This class encompasses Fix, message passing algorithms including Belief and Survey Propagation guided decimation (with bounded or mildly growing number of rounds), and local algorithms on the factor graph. This is the first hardness result for any class of algorithms at clause density within a constant factor of that achieved by Fix. Our proof establishes and leverages a new many-way overlap gap property tailored to random k-SAT.

关键词： random k-SAT average-case complexity algorithmic phase transition low degree polynomial hardness overlap gap property

来源：评论

学校读者我要写书评

暂无评论

Extracting Randomness from Samplable Distributions, Revisited 64

Extracting Randomness from Samplable Distributions, Revisite...

引用

64th Annual IEEE Symposium on the Foundations of Computer Science (FOCS)

作者： Ball, Marshall Goldin, Eli Dachman-Soled, Dana Mutreja, Saachi NYU New York NY 10003 USA Univ Maryland College Pk MD USA Columbia Univ New York NY USA

ISBN: (纸本)9798350318944

Randomness extractors provide a generic way of converting sources of randomness that are merely unpredictable into almost uniformly random bits. While in general, deterministic randomness extraction is impossible, it is possible if the source has some structural constraints. While much of the literature on deterministic extraction has focused on sources with strong independence properties, a natural class where deterministic extraction is possible is sources that can sampled by a polynomial size circuit, Levin [SIAM J Comp'86]. Trevisan and Vadhan [FOCS'00] explicitly constructed deterministic randomness extractors for this class of sources, assuming very strong circuit lower bounds. We suggest that there is perhaps an even more reasonable model of natural sources of randomness than Levin's: sources sampled by polynomial size quantum circuits. Under a suitable circuit lower bound, we show that Trevisan and Vadhan's extractor indeed works for this class. Along the way, we substantially improve their analysis in the classical case, showing that a circuit lower bound against NP-circuits suffice in the classical case (as opposed to a lower bounds on Sigma(5)-circuits, as shown by Trevisan and Vadhan). Moreover, we show that under this assumption, it is possible to handle sources sampled by postselecting circuits (a variant of nondeterministic circuits). We show that this model is sufficient to capture randomness extraction in the presence of efficiently computable leakage.

关键词： average-case complexity quantum computing randomness in computing

来源：评论

学校读者我要写书评

暂无评论

Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits 16

Super-Linear Gate and Super-Quadratic Wire Lower Bounds for ...

引用

48th Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Kane, Daniel M. Williams, Ryan Univ Calif San Diego Dept Math 9500 Gilman Dr La Jolla CA 92093 USA Univ Calif San Diego Dept Comp Sci 9500 Gilman Dr La Jolla CA 92093 USA Stanford Univ Dept Comp Sci 353 Serra Mall Stanford CA 94305 USA Simons Inst Theory Comp Berkeley CA USA

ISBN: (纸本)9781450341325

In order to formally understand the power of neural computing, we first need to crack the frontier of threshold circuits with two and three layers, a regime that has been surprisingly intractable to analyze. We prove the first super-linear gate lower bounds and the first super-quadratic wire lower bounds for depth-two linear threshold circuits with arbitrary weights, and depth-three majority circuits computing an explicit function. We prove that for all epsilon >> root log(n)/n, the linear-time computable Andreev's function cannot be computed on a (1/2 + epsilon)-fraction of n-bit inputs by depth-two circuits of o(epsilon(3)n(3/2)/log(3) n) gates, nor can it be computed with o(epsilon(3)n(5/2)/log(7/2) n) wires. This establishes an average-case "size hierarchy" for threshold circuits, as Andreev's function is computable by uniform depth-two circuits of o(n(3)) linear threshold gates, and by uniform depth-three circuits of O(n) majority gates. We present a new function in P based on small-biased sets, which we prove cannot be computed by a majority vote of depth-two threshold circuits of o(n(3/2)/ log(3) n) gates, nor with o(n(5/2)/ log(7/2) n) wires. We give tight average-case (gate and wire) complexity results for computing PARITY with depth-two threshold circuits;the answer turns out to be the same as for depth-two majority circuits. The key is a new method for analyzing random restrictions to linear threshold functions. Our main analytical tool is the Littlewood-Offord Lemma from additive combinatorics.

关键词： average-case complexity circuit complexity random restrictions threshold circuits Littlewood-Offord problems

来源：评论

学校读者我要写书评

暂无评论

On Approximating by Polynomials and Several Related Models

On Approximating by Polynomials and Several Related Models

引用

作者： Huang, Xuangui Northeastern University

学位级别：Ph.D., Doctor of Philosophy

We study the problem of approximating Boolean functions under two different notions of approximation, using three different but related models. 1. We consider the approximation to be point-wise, and we use real-valued polynomials to approximate. We study the degree in conjunction with the weight of such approximating polynomials. We show a tight approximate degree-weight result for any symmetric functions. We also show an approximate degree-weight result for bounded-width CNFs, and “does not fool” theorem for symmetric functions on a relaxation of indistinguishability. Additionally, we reprove the following known approximate degree lower bounds in the language of indistinguishability. 2. We consider the approximation to be over uniform inputs, which coincides with the notion of average-case complexity. We use the model of AC0 -XOR circuits, which are constant-depth circuits with a layer of parity gates (or their negations) at the bottom. We study the problem of approximating by such circuits via the perspective of affine extractors. We show that good affine extractors can be computed by small depth-4 AC0 -XOR circuits, indicating that proving strong average-case lower bounds against such circuits are hard. We also show that one-sided affine extractors can be computed by small depth-3 AC0 -XOR circuits, and separate these circuits from parity decision trees. 3. We again consider the same notion of approximation, and we use low-rank matrices to approximate. This is exactly the famous problem of constructing explicit rigid matrices. We construct matrices that are rigid even in the strong average-case. The main ingredients of the proof concern about point-wise approximating Boolean functions by linear combinations (with real coefficients) of functions from a simple class, which is the class of low-rank matrices here. Motivated by recent development of such ingredients, we also show direct product results for such approximate linear combinations.

关键词： Affine extractors Approximate degree-weight average-case complexity Indistinguishability Matrix rigidity Polynomials

来源：评论

学校读者我要写书评

暂无评论

Excluding PH Pessiland 13

Excluding PH Pessiland

引用

13th Innovations in Theoretical Computer Science Conference, ITCS 2022

作者： Hirahara, Shuichi Santhanam, Rahul Principle of Informatics Research Division National Institute of Informatics Tokyo Japan Department of Computer Science University of Oxford United Kingdom

ISBN: (纸本)9783959772174

Heuristica and Pessiland are "worlds" of average-case complexity [Impagliazzo95] that are considered unlikely but that current techniques are unable to rule out. Recently, [Hirahara20] considered a PH (Polynomial Hierarchy) analogue of Heuristica, and showed that to rule it out, it would be sufficient to prove the NP-completeness of the problem GapMINKTPH of estimating the PH-oracle time-bounded Kolmogorov complexity of a string. In this work, we analogously define "PH Pessiland" to be a world where PH is hard on average but PH-computable pseudo-random generators do not exist. We unconditionally rule out PH-Pessiland in both non-uniform and uniform settings, by showing that the distributional problem of computing PH-oracle time-bounded Kolmogorov complexity of a string over the uniform distribution is complete for an (error-prone) average-case analogue of PH. Moreover, we show the equivalence between error-prone average-case hardness of PH and the existence of PH-computable pseudorandom generators. © Shuichi Hirahara and Rahul Santhanam;licensed under Creative Commons License CC-BY 4.0

关键词： average-case complexity Meta-complexity Pseudorandomness

来源：评论

学校读者我要写书评

暂无评论

On the computation of rational solutions of underdetermined systems over a finite field*,**

引用

JOURNAL OF complexity 2023年 75卷

作者： Gimenez, Nardo Matera, Guillermo Perez, Mariana Privitelli, Melina Univ Nacl Hurlingham Inst Tecnol Ingeniena Av Villa Tesei RA-1688 Buenos Aires Argentina Univ Nacl Gen Sarmiento Inst Desarrollo Humano JM Gutierrez 1150 RA-1613 Buenos Aires Argentina Natl Council Sci & Technol CONICET Santa Fe Argentina Univ Nacl Gen Sarmiento Inst Ciencias JM Gutierrez 1150 RA-1613 Buenos Aires Argentina

We design and analyze an algorithm for computing solutions with coefficients in a finite field Fq of underdetermined systems defined over Fq. The algorithm is based on reductions to zero-dimensional searches. The searches are performed on "vertical strips", namely parallel linear spaces of suitable dimension in a given direction. Our results show that, on average, less than three searches suffice to obtain a solution of the original system, with a probability of success which grows exponentially with the number of searches. The analysis of our algorithm relies on results on the probability that the solution set (over the algebraic closure of Fq) of a random system with coefficients in Fq satisfies certain geometric and algebraic properties which is of independent interest.(c) 2022 Elsevier Inc. All rights reserved.

关键词： Finite fields Underdetermined systems Rational solutions Reduced regular sequences average-case complexity Probability of success

来源：评论

学校读者我要写书评

暂无评论

P-comp versus P-samp questions on average polynomial domination

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2001年第10期E84D卷 1402-1410页

作者： Aida, S Tsukiji, T Nagoya Univ Grad Sch Human Informat Nagoya Aichi 4660826 Japan

In the theory of average-case NP-completeness, Levin introduced the polynomial domination and Gurevich did the average polynomial domination. Ben-David et al. proved that if P-samp (the class of polynomial-time samplable, distributions) is polynomially dominated by P-comp (the class of polynomial-time computable distributions) then there exists no strong one-way function. This result will be strengthened by relaxing the assumption from the polynomial domination to the average polynomial domination. Our results also include incompleteness for average polynomial-time one-one reducibility from (NP, P-samp) to (NP, P-comp). Th derive these and other related results, a prefix-search algorithm presented by Ben-David et al., will be modified to survive the average polynomial domination.

关键词： average-case complexity polynomial-time computability polynomial-time samplability domination

来源：评论

学校读者我要写书评

暂无评论

IS IT POSSIBLE TO IMPROVE YAO'S XOR LEMMA USING REDUCTIONS THAT EXPLOIT THE EFFICIENCY OF THEIR ORACLE?

引用

COMPUTATIONAL complexity 2023年第1期32卷 5-5页

作者： Shaltiel, Ronen Univ Haifa Dept Comp Sci 65 Hanamal St IL-3303221 Haifa Israel

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-1) circle plus ... circle plus f(X-t) for sufficiently large t has hardness 1/2 + epsilon for P/poly. Known proofs of this lemma cannot achieve epsilon = 1/k(omega(1)) k.(1), and even for epsilon = 1/k, we do not know how to replace P/poly by AC(0) [parity] (the class of constant depth circuits with the gates {and,or,not,parity} of unbounded fan-in). Grinberg, Shaltiel and Viola (FOCS 2018) (building on a sequence of earlier works) showed that these limitations cannot be circumvented by black-box reductions. Namely, by reductions Red((center dot)) that given oracle access to a function D that violates the conclusion of Yao's XOR lemma, implement a circuit that violates the assumption of Yao's XOR lemma. There are a few known reductions in the related literature on worstcase to average-case reductions that are non-black-box. Specifically, the reductions of Gutfreund, Shaltiel and Ta-Shma (Computational complexity 2007) and Hirahara (FOCS 2018)) are "class reductions" that are only guaranteed to succeed when given oracle access to an oracle D from some efficient class of algorithms. These works seem to circumvent some black-box impossibility results. In this paper, we extend the previous limitations of Grinberg, Shaltiel and Viola to several types of class reductions, giving evidence that class reductions cannot yield the desired improvements in Yao's XOR lemma. To the best of our knowledge, this is the first limitation on reductions for hardness amplification that applies to class reductions. Our technique imitates the previous lower bounds for black-box reductions, replacing the inefficient oracle used in that proof, with an efficient one that is based on limited independence, and developing tools to deal with the technical difficulties that a

关键词： average-case complexity Yao's XOR lemma black-boxreductions

来源：评论

学校读者我要写书评

暂无评论

NON-BLACK-BOX WORST-case TO average-case REDUCTIONS WITHIN NP

引用

SIAM JOURNAL ON COMPUTING 2023年第6期52卷 349-382页

作者： Hirahara, Shuichi Natl Inst Informat Tokyo 1018430 Japan

There are significant obstacles to establishing an equivalence between the worst-case and average-case hardness of NP. Several results suggest that black-box worst-case to averagecase reductions are not likely to be used for reducing any worst-case problem outside coNP/poly to a distributional NP problem. This paper overcomes the barrier. We present the first non-blackbox worst-case to average-case reduction from a problem conjectured to be outside coNP/poly to a distributional NP problem. Specifically, we consider the minimum time-bounded Kolmogorov complexity problem (MINKT) and prove that there exists a zero-error randomized polynomial-time algorithm approximating the minimum time-bounded Kolmogorov complexity k within an additive error (sic)(root k) if its average-case version admits an errorless heuristic polynomial-time algorithm. We observe that the approximation version of MINKT is Random 3SAT-hard, and more generally it is harder than avoiding any polynomial-time computable hitting set generator that extends its seed of length n by (sic)(root n), which provides strong evidence that the approximation problem is outside coNP/poly and thus our reductions are non-black-box. Our reduction can be derandomized at the cost of the quality of the approximation. We also show that, given a truth table of size 2(n), approximating the minimum circuit size within a factor of 2((1-epsilon)n) is in \sansB NP for some constant epsilon > 0 iff its averagecase version is easy. Our results can be seen as a new approach for excluding Heuristica. In particular, proving NP-hardness of the approximation versions of MINKT or the minimum circuit size problem is sufficient for establishing an equivalence between the worst-case and average-case hardness of NP.

关键词： average-case complexity non-black-box reduction time-bounded Kolmogorov complexity minimum circuit size problem

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：