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

55th Annual ACM Symposium on Theory of Computing (STOC) part of the ACM Federated Computing Research Conference (FCRC)

作者： Hirahara, Shuichi Shimizu, Nobutaka Natl Inst Informat Tokyo Japan Tokyo Inst Technol Tokyo Japan

ISBN: (纸本)9781450399135

Strong (resp. weak) average-case hardness refers to the properties of a computational problem in which a large (resp. small) fraction of instances are hard to solve. We develop a general framework for proving hardness self-amplification, that is, the equivalence between strong and weak average-case hardness. Using this framework, we prove hardness self-amplification for popular problems, such as matrix multiplication, online matrix-vector multiplication, triangle counting of Erdos-Renyi random graphs, and the planted clique problem. As a corollary, we obtain the first search-to-decision reduction for the planted clique problem in a high-error regime. Our framework simplifies, improves, and unifies the previous hardness self-amplification results. Our approach uses a one-query upward self-reduction, that is, a reduction that maps a small instance to a large instance. We demonstrate that this reduction yields hardness self-amplification if the bipartite graph, whose left and right vertices correspond to small and large instances, respectively, has an expansion property. Our key technical contribution is to show the expansion property of the bipartite graph naturally constructed from the planted clique problem by using the coupling method of Markov chains.

关键词： average-case complexity Hardness Amplification

来源：评论

学校读者我要写书评

暂无评论

Lattice-Based Methods Surpass Sum-of-Squares in Clustering 35

Lattice-Based Methods Surpass Sum-of-Squares in Clustering

引用

35th Conference on Learning Theory (COLT)

作者： Zadik, Ilias Song, Min Jae Wein, Alexander S. Bruna, Joan MIT Dept Math Cambridge MA 02139 USA NYU Courant Inst Math Sci New York NY 10003 USA Georgia Inst Technol Algorithms & Randomness Ctr Atlanta GA 30332 USA NYU Ctr Data Sci New York NY 10003 USA Flatiron Inst Ctr Computat Math New York NY USA

In this work we show that for an important case of the canonical clustering task of a d-dimensional Gaussian mixture with unknown (and possibly degenerate) covariance, a lattice-based polynomial-time method can provably succeed with the statistically-optimal sample complexity of d + 1 samples. This is in contrast with the evidence of "computational hardness" for this task, as suggested by the previously established failure of low-degree methods and the Sum-of-Squares hierarchy to succeed with access to (O) over tilde (d(3/2)) and (O) over tilde (d(2)) samples, respectively.(1)

关键词： statistical-to-computational gaps lattice basis reduction sum-of-squares lower bounds average-case complexity

来源：评论

学校读者我要写书评

暂无评论

On the Implementation of Monotone Boolean Functions by Memoryless Programs

引用

MOSCOW UNIVERSITY MATHEMATICS BULLETIN 2022年第3期77卷 136-143页

作者： Chashkin, A., V Lomonosov Moscow State Univ Fac Mech & Math Chair Discrete Math Moscow Russia

The average-case complexity of computing monotone Boolean functions by straight-line programs without memory with a conditional stop in the basis of all Boolean functions of at most two variables is considered. For the set of all monotone Boolean functions of n variables, Shannon-type upper and lower bounds for the average-case complexity are established for n -> infinity.

关键词： monotone Boolean functions formulas average-case complexity

来源：评论

学校读者我要写书评

暂无评论

Worst-case to average-case Reductions via Additive Combinatorics 2022

Worst-Case to Average-Case Reductions via Additive Combinato...

引用

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

作者： Asadi, Vahid R. Golovnev, Alexander Gur, Tom Shinkar, Igor Univ Waterloo Waterloo ON Canada Georgetown Univ Washington DC USA Univ Warwick Warwick England Simon Fraser Univ Burnaby BC Canada

ISBN: (纸本)9781450392648

We present a new framework for designing worst-case to averagecase reductions. For a large class of problems, it provides an explicit transformation of algorithms running in time.. that are only correct on a small (subconstant) fraction of their inputs into algorithms running in time (O) over tilde (T) that are correct on all inputs. Using our framework, we obtain such efficient worst-case to average-case reductions for fundamental problems in a variety of computational models;namely, algorithms for matrix multiplication, streaming algorithms for the online matrix-vector multiplication problem, and static data structures for all linear problems as well as for the multivariate polynomial evaluation problem. Our techniques crucially rely on additive combinatorics. In particular, we show a local correction lemma that relies on a new probabilistic version of the quasi-polynomial Bogolyubov-Ruzsa lemma.

关键词： average-case complexity matrix multiplication data structures

来源：评论

学校读者我要写书评

暂无评论

Algorithms and Barriers in the Symmetric Binary Perceptron Model 63

Algorithms and Barriers in the Symmetric Binary Perceptron M...

引用

63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS)

作者： Gamarnik, David Kizildag, Eren C. Perkins, Will Xu, Changji MIT Cambridge MA 02139 USA Univ Illinois Chicago IL USA Harvard Univ Cambridge MA 02138 USA

ISBN: (纸本)9781665455190

The binary (or Ising) perceptron is a toy model of a single-layer neural network and can be viewed as a random constraint satisfaction problem with a high degree of connectivity. The model and its symmetric variant, the symmetric binary perceptron (SBP), have been studied widely in statistical physics, mathematics, and machine learning. The SBP exhibits a dramatic statistical-to-computational gap: the densities at which known efficient algorithms find solutions are far below the threshold for the existence of solutions. Furthermore, the SBP exhibits a striking structural property: at all positive constraint densities almost all of its solutions are `totally frozen' singletons separated by large Hamming distance [1], [2]. This suggests that finding a solution to the SBP may be computationally intractable. At the same time, however, the SBP does admit polynomial-time search algorithms at low enough densities. A conjectural explanation for this conundrum was put forth in [3]: efficient algorithms succeed in the face of freezing by finding exponentially rare clusters of large size. However, it was discovered recently that such rare large clusters exist at all subcritical densities, even at those well above the limits of known efficient algorithms [4]. Thus the driver of the statistical-to-computational gap exhibited by this model remains a mystery. In this paper, we conduct a different landscape analysis to explain the statistical-to-computational gap exhibited by this problem. We show that at high enough densities the SBP exhibits the multi Overlap Gap Property (m-OGP), an intricate geometrical property known to be a rigorous barrier for large classes of algorithms. Our analysis shows that the m-OGP threshold (a) is well below the satisfiability threshold;and (b) matches the best known algorithmic threshold up to logarithmic factors as m ->infinity. We then prove that the m-OGP rules out the class of stable algorithms for the SBP above this threshold. We conjecture tha

关键词： Binary perceptron overlap gap property statistical-to-computational gap random CSP average-case complexity neural networks

来源：评论

学校读者我要写书评

暂无评论

The permutation-path coloring problem on trees

The permutation-path coloring problem on trees

引用

4th Latin American Theoretical Informatics International Conference (LATIN 2000)

作者： Corteel, S Valencia-Pabon, M Gardy, D Barth, D Denise, A Univ Paris 11 LRI F-91405 Orsay France Univ Versailles PRiSM F-78035 Versailles France

In this paper we first show that the permutation-path coloring problem is NP-hard even for very restrictive instances like involutions, which are permutations that contain only cycles of length at most two, on both binary trees and on trees having only two vertices with degree greater than two, and for circular permutations, which are permutations that contain exactly one cycle, on trees with maximum degree greater than or equal to 4. We calculate a lower bound on the average complexity of the permutation-path coloring problem on arbitrary networks. Then we give combinatorial and asymptotic results for the permutation-path coloring problem on linear networks in order to show that the average number of colors needed to color any permutation on a linear network on n vertices is n/4 + o(n). We extend these results and obtain an upper bound on the average complexity of the permutation-path coloring problem on arbitrary trees, obtaining exact results in the case of generalized star trees. Finally we explain how to extend these results for the involutions-path coloring problem on arbitrary trees. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： average-case complexity routing permutation path coloring tree networks NP-completeness

来源：评论

学校读者我要写书评

暂无评论

Planted Clique Conjectures Are Equivalent 2024

Planted Clique Conjectures Are Equivalent

引用

56th Annual ACM Symposium on Theory of Computing (STOC)

作者： Hirahara, Shuichi Shimizu, Nobutaka Natl Inst Informat Tokyo Japan Tokyo Inst Technol Tokyo Japan

The planted clique conjecture states that no polynomial-time algorithm can find a hidden clique of size k > k(2) /n if and only if the planted clique conjecture holds. The equivalence among search versions identifi... 详细信息

ISBN: (纸本)9798400703836

The planted clique conjecture states that no polynomial-time algorithm can find a hidden clique of size k << root n in an n -vertex Erdos-Renyi random graph with a k << -clique planted. In this paper, we prove the equivalence among many (in fact, most) variants of planted clique conjectures, such as search versions with a success probability exponentially close to 1 and with a non-negligible success probability, a worst-case version (the k -clique problem on incompressible graphs), decision versions with small and large success probabilities, and decision versions with adversarially chosen : and binomially distributed k. In particular, we establish the equivalence between the planted clique problem introduced by Jerrum and Kucera and its decision version suggested by Saks in the 1990s. Moreover, the equivalence among decision versions identifies the optimality of a simple edge counting algorithm: By counting the number of edges, one can efficiently distinguish an n-vertex random graph from a random graph with a k -clique planted with probability Theta (k(2)/n) for any k <= root n. We show that for any k no polynomialtime algorithm can distinguish these two random graphs with probability >> k(2) /n if and only if the planted clique conjecture holds. The equivalence among search versions identifies the first one-way function that admits a polynomial-time security-preserving selfreduction from exponentially weak to strong one-way functions. These results reveal a detection-recovery gap in success probabilities for the planted clique problem. We also present another equivalence between the existence of a refutation algorithm for the planted clique problem and an average-case polynomial-time algorithm for the k-clique problem with respect to the Erdos-Renyi random graph.

关键词： platned clique hardness amplification average-case complexity

来源：评论

学校读者我要写书评

暂无评论

Hardness Amplification Proofs Require Majority 08

Hardness Amplification Proofs Require Majority

引用

14th Annual ACM International Symposium on Theory of Computing

作者： Shaltiel, Ronen Viola, Emanuele Univ Haifa Dept Comp Sci IL-31999 Haifa Israel Columbia Univ New York NY 10027 USA

ISBN: (纸本)9781605580470

Hardness amplification is the fundamental task of converting a delta-hard function f : {0, 1}(n) -> {0, 1} into a (1/2 - epsilon)-hardfunction Amp(f), where f is gamma-hard if small circuits fail to compute f on at least a gamma fraction of the inputs. Typically, epsilon, delta are small (and delta = 2(-k) captures the case where f is worst-case hard). Achieving epsilon = 1/n(w(1)) is a prerequisite for cryptography and most pseudorandom-generator constructions. In this paper we study the complexity of black-box proofs of hardness amplification. A class of circuits V proves a hardness amplification result if for any function h that agrees with Amp(f) on a 1/2 + epsilon fraction of the inputs there exists an oracle circuit D is an element of D such that D-h agrees with f on a 1 - delta fraction of the inputs. We focus on the case where every D is an element of D makes non-adaptive queries to h. This setting captures most hardness amplification techniques. We prove two main results: 1. The circuits in D "can be used" to compute the majority function on 1/epsilon bits. In particular, these circuits have large depth when epsilon <= 1/poly log n. 2. The circuits in D must make Omega (log(1/delta)/epsilon(2)) oracle queries. Both our bounds on the depth and on the number of queries are tight up to constant factors. Our results explain why hardness amplification techniques have failed to transform known lower bounds against constant-depth circuit classes into strong average-case lower bounds. When coupled with the celebrated "Natural Proofs" result by Razborov and Rudich (J. CSS '97) and the pseudorandom functions by Naor and Reingold (J. ACM '04), Our results show that standard techniques for hardness amplification can only be applied to those circuit classes for which standard techniques cannot prove circuit lower bounds. Our results reveal a contrast between Yao's XOR Lemma (Amp(f) := f(x(1)) circle plus ... circle plus f(x(t)) is an element of {0, 1}) and the Direct-Pr

关键词： average-case complexity hardness amplification majority constant-depth circuits black-box natural proofs

来源：评论

学校读者我要写书评

暂无评论

An average-case Lower Bound Against ACC⁰ 13th

An Average-Case Lower Bound Against ACC<SUP>0</SUP>

引用

13th Latin American Theoretical Informatics Symposium (LATIN)

作者： Chen, Ruiwen Oliveira, Igor C. Santhanam, Rahul Univ Oxford Dept Comp Sci Oxford England

ISBN: (纸本)9783319774046;9783319774039

In a seminal work, Williams [22] showed that NEXP (non-deterministic exponential time) does not have polynomial-size ACC(0) circuits. Williams' technique inherently gives a worst-case lower bound, and until now, no average-case version of his result was known. We show that there is a language L in NEXP and a function epsilon(n) = 1/log(n)(omega(1)) such that no sequence of polynomial size ACC(0) circuits solves L on more than a 1/2+epsilon(n) fraction of inputs of length n for all large enough n. Complementing this result, we give a nontrivial pseudo-random generator against polynomial-size AC(0) [6] circuits. We also show that learning algorithms for quasi-polynomial size ACC(0) circuits running in time 2(n)/n(omega) (1) imply lower bounds for the randomised exponential time classes RE (randomized time 2(O(n)) with one-sided error) and ZPE/1 (zero-error randomized time 2(O(n)) with 1 bit of advice) against polynomial size ACC(0) circuits. This strengthens results of Oliveira and Santhanam [15].

关键词： Circuit lower bounds average-case complexity Pseudorandomness Learning and natural properties

来源：评论

学校读者我要写书评

暂无评论

Sum-of-Squares Lower Bounds for Densest k-Subgraph 2023

Sum-of-Squares Lower Bounds for Densest k-Subgraph

引用

55th Annual ACM Symposium on Theory of Computing (STOC) part of the ACM Federated Computing Research Conference (FCRC)

作者： Jones, Chris Potechin, Aaron Rajendran, Goutham Xu, Jeff Bocconi Univ Milan Italy Univ Chicago Chicago IL USA Carnegie Mellon Univ Pittsburgh PA USA

ISBN: (纸本)9781450399135

Given a graph and an integer.., Densest.. -Subgraph is the algorithmic task of finding the subgraph on.. vertices with the maximum number of edges. This is a fundamental problem that has been subject to intense study for decades, with applications spanning a wide variety of fields. The state-of-the-art algorithm is an.. (epsilon 1/4)factor approximation (for any epsilon> 0) due to Bhaskara et al. [STOC '10]. Moreover, the so-called log-density framework predicts that this is optimal, i.e. it is impossible for an efficient algorithm to achieve an.. (N1/4-epsilon)-factor approximation. In the average case, Densest-Subgraph is a prototypical noisy inference task which is conjectured to exhibit a statistical-computational gap. In this work, we provide the strongest evidence yet of hardness for Densest-Subgraph by showing matching lower bounds against the powerful Sum-of-Squares (SoS) algorithm, a meta-algorithm based on convex programming that achieves state-of-art algorithmic guarantees for many optimization and inference problems. For K <= 12, we obtain a degree. SoS lower bound for the hard regime as predicted by the log-density framework. To show this, we utilize the modern framework for proving SoS lower bounds on average-case problems pioneered by Barak et al. [FOCS '16]. A key issue is that small denser-than-average subgraphs in the input will greatly affect the value of the candidate pseudoexpectation operator around the subgraph. To handle this challenge, we devise a novel matrix factorization scheme based on the positive minimum vertex separator. We then prove an intersection tradeoff lemma to show that the error terms when using this separator are indeed small.

关键词： Densest k-Subgraph average-case complexity Sum-of-Squares Lower Bounds

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：