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

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

作者： Girish, Uma Sinha, Makrand Tal, Avishay Wu, Kewen Princeton Univ Princeton NJ 08544 USA Univ Illinois Champaign IL USA Univ Calif Berkeley Berkeley CA USA

ISBN: (纸本)9798350318944

The level-k l(1)-Fourier weight of a boolean function refers to the sum of absolute values of its level-k Fourier coefficients. Fourier growth refers to the growth of these weights as k grows. It has been extensively studied for various computational models, and bounds on the Fourier growth, even for the first few levels, have proven useful in learning theory, circuit lower bounds, pseudorandomness, and quantum-classical separations. In this work, we investigate the Fourier growth of certain functions that naturally arise from communication protocols for XOR functions (partial functions evaluated on the bitwise XOR of the inputs x and y to Alice and Bob). If a protocol C computes an XOR function, then C(x, y) is a function of the parity x. y. This motivates us to analyze the XOR-fiber of the communication protocol C, defined as h(z) := E-x,E-y[C(x, y)|x circle plus y = z]. We present improved Fourier growth bounds for the XOR-fibers of randomized protocols that communicate d bits. For the first level, we show a tight O(root d) bound and obtain a new coin theorem, as well as an alternative proof for the tight randomized communication lower bound for the Gap-Hamming problem. For the second level, we show an d(3/2)center dot polylog(n) bound, which improves the previous O(d(2)) bound by Girish, Raz, and Tal (ITCS 2021) and implies a polynomial improvement on the randomized communication lower bound for the XOR-lift of the Forrelation problem, which extends the quantum-classical gap for this problem. Our analysis is based on a new way of adaptively partitioning a relatively large set in Gaussian space to control its moments in all directions. We achieve this via martingale arguments and allowing protocols to transmit real values. We also show a connection between Fourier growth and lifting theorems with constant-sized gadgets as a potential approach to prove optimal bounds for the second level and beyond.

关键词： Fourier growth communication protocol analysis of boolean functions quantum-classical separation

来源：评论

学校读者我要写书评

暂无评论

Approximating the distance to monotonicity of boolean functions

引用

RANDOM STRUCTURES & ALGORITHMS 2022年第2期60卷 233-260页

作者： Pallavoor, Ramesh Krishnan S. Raskhodnikova, Sofya Waingarten, Erik Boston Univ Dept Comp Sci 111 Cummington St Boston MA 02215 USA Columbia Univ Dept Comp Sci New York NY 10027 USA

We design a nonadaptive algorithm that, given oracle access to a function f:{0,1}(n) -> {0,1} which is alpha-far from monotone, makes poly(n,1/alpha) queries and returns an estimate that, with high probability, is an (O) over tilde(root n)-approximation to the distance of f to monotonicity. The analysis of our algorithm relies on an improvement to the directed isoperimetric inequality of Khot, Minzer, and Safra (SIAM J. Comput., 2018). Furthermore, we rule out a poly(n,1/alpha)-query nonadaptive algorithm that approximates the distance to monotonicity significantly better by showing that, for all constant kappa>0, every nonadaptive n(1/2-kappa)-approximation algorithm for this problem requires 2(n kappa) queries. This answers a question of Seshadhri (Property Testing Review, 2014) for the case of nonadaptive algorithms. We obtain our lower bound by proving an analogous bound for erasure-resilient (and tolerant) testers. Our method also yields the same lower bounds for unateness and being a k-junta.

关键词： analysis of boolean functions property testing sublinear algorithms tolerant and erasure-resilient testing

来源：评论

学校读者我要写书评

暂无评论

Improved Optimal Testing Results from Global Hypercontractivity 63

Improved Optimal Testing Results from Global Hypercontractiv...

引用

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

作者： Kaufman, Tali Minzer, Dor Bar Ilan Univ Ramat Gan Israel MIT Cambridge MA 02139 USA

ISBN: (纸本)9781665455190

The problem of testing low-degree polynomials has received significant attention over the years due to its importance in theoretical computer science, and in particular in complexity theory. The problem is specified by three parameters: field size q, degree d and proximity parameter delta, and the goal is to design a tester making as few as possible queries to a given function, which is able to distinguish between the case the given function has degree at most d, and the case the given function is delta-far from any degree d function. With respect to these parameters, we say that a tester is optimal if it makes O(q(t) + 1/delta) queries, where t = t(d, q) is the testing dimension of d, q (defined as the minimum integer so that for all g : F-q(n)-> F-q of degree more than d, there is a subspace of dimension t on which their restriction has degree exceeding d). For the field of size q, such tester was first given by Bhattacharyya et al. for q = 2, and later by Haramaty et al. [7] for all prime powers q. In fact, they showed that the natural t-flat tester is an optimal tester for the Reed-Muller code, for an appropriate t. Here, the t-flat tester is the tester that picks a uniformly random affine subspace A of dimension t, and checks that deg(f| (A)) <= d. Their analysis proves that the dependency of the t-flat tester on delta and d is optimal, however the dependency on the field size, i.e. the hidden constant in the O, is a tower-type function in q. We improve the result of Haramaty et al., showing that the dependency on the field size is polynomial. Our technique also applies in the more general setting of lifted affine invariant codes, and gives the same polynomial dependency on the field size. This answers a problem raised in [6]. Our approach significantly deviates from the strategy taken in earlier works [2], [7], [6], and is based on studying the structure of the collection of erroneous subspaces, i.e. subspaces A such that f| (A) has degree greater than d. Towa

关键词： Reed-Muller Code Optimal Testing Global Hypercontractivity analysis of boolean functions

来源：评论

学校读者我要写书评

暂无评论

An Invariance Principle for the Multi-slice, with Applications 62

An Invariance Principle for the Multi-slice, with Applicatio...

引用

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

作者： Braverman, Mark Khot, Subhash Lifshitz, Noam Minzer, Dor Princeton Univ Dept Comp Sci Princeton NJ 08544 USA NYU Courant Inst Math Sci Dept Comp Sci New York NY 10012 USA Hebrew Univ Jerusalem Dept Math Jerusalem Israel MIT Dept Math Cambridge MA 02139 USA

ISBN: (纸本)9781665420556

Given an alphabet size m is an element of N thought of as a constant, and (k) over right arrow = (k(1), ... , k(m)) whose entries sum of up n, the (k) over right arrow -multi-slice is the set of vectors x is an element of [m](n) in which each symbol i is an element of [m] appears precisely k(i) times. We show an invariance principle for low-degree functions over the multi-slice, to functions over the product space ([m](n), mu(n)) in which mu(i) = k(i)/n. This answers a question raised by [21]. As applications of the invariance principle, we show: 1) An analogue of the "dictatorship test implies computational hardness" paradigm for problems with perfect completeness, for a certain class of dictatorship tests. Our computational hardness is proved assuming a recent strengthening of the Unique-Games Conjecture, called the Rich 2-to-1 Games Conjecture. Using this analogue, we show that assuming the Rich 2-to-1 Games Conjecture, (a) there is an r-ary CSP P-r for which it is NP-hard to distinguish satisfiable instances of the CSP and instances that are at most 2r+1/2r + o(1) satisfiable, and (b) hardness of distinguishing 3-colorable graphs, and graphs that do not contain an independent set of size o(1). 2) A reduction of the problem of studying expectations of products of functions on the multi-slice to studying expectations of products of functions on correlated, product spaces. In particular, we are able to deduce analogues of the Gaussian bounds from [38] for the multi-slice. 3) In a companion paper, we show further applications of our invariance principle in extremal combinatorics, and more specifically to proving removal lemmas of a wide family of hypergraphs H called zeta-forests, which is a natural extension of the well-studied case of matchings.

关键词： PCP Hardness of approximation analysis of boolean functions

来源：评论

学校读者我要写书评

暂无评论

Open Problem: Properly learning decision trees in polynomial time? 35

Open Problem: Properly learning decision trees in polynomial...

引用

35th Conference on Learning Theory (COLT)

作者： Blanc, Guy Lange, Jane Qiao, Mingda Tan, Li-Yang Stanford Stanford CA 94305 USA MIT Cambridge MA USA

The authors recently gave an n(O(log log n)) time membership query algorithm for properly learning decision trees under the uniform distribution (Blanc et al., 2021). The previous fastest algorithm for this problem ran in n(O(log n)) time, a consequence of Ehrenfeucht and Haussler (1989)'s classic algorithm for the distribution-free setting. In this article we highlight the natural open problem of obtaining a polynomial-time algorithm, discuss possible avenues towards obtaining it, and state intermediate milestones that we believe are of independent interest.

关键词： Decision trees proper learning analysis of boolean functions

来源：评论

学校读者我要写书评

暂无评论

Proof of Tomaszewski?s conjecture on randomly signed sums

引用

ADVANCES IN MATHEMATICS 2022年 407卷

作者： Keller, Nathan Klein, Ohad Bar Ilan Univ Dept Math Ramat Gan Israel

We prove the following conjecture, due to Tomaszewski (1986): Let X = sigma(n)(i=1) a(i)x(i), where sigma(i)a(i)(2) = 1 and each xi is a uniformly random sign. Then Pr[|X| = 1/2. Our main novel tools are local concent... 详细信息

We prove the following conjecture, due to Tomaszewski (1986): Let X = sigma(n)(i=1) a(i)x(i), where sigma(i)a(i)(2) = 1 and each xi is a uniformly random sign. Then Pr[|X| <= 1] >= 1/2. Our main novel tools are local concentration inequalities and an improved Berry-Esseen inequality for Rademacher sums. (C) 2022 Elsevier Inc. All rights reserved.

关键词： Tail inequalities Probabilistic inequalities Combinatorics analysis of boolean functions

来源：评论

学校读者我要写书评

暂无评论

AND Testing and Robust Judgement Aggregation 2020

AND Testing and Robust Judgement Aggregation

引用

52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Filmus, Yuval Lifshitz, Noam Minzer, Dor Mossel, Elchanan Technion Dept Comp Sci Haifa Israel Hebrew Univ Jerusalem Einstein Inst Math Jerusalem Israel Inst Adv Study Olden Lane Princeton NJ 08540 USA MIT Dept Math Cambridge MA 02139 USA MIT IDSS 77 Massachusetts Ave Cambridge MA 02139 USA

ISBN: (纸本)9781450369794

A function f : {0, 1}(n) -> {0, 1} is called an approximate AND-homomorphism if choosing x, y is an element of {0, 1}(n) uniformly at random, we have that f (x boolean AND y) = f (x) boolean AND f (y) with probability at least 1 - epsilon, where x boolean AND y = (x(1) boolean AND y(1), ... , x(n) boolean AND y(n)). We prove that if f : {0, 1}(n) -> {0, 1} is an approximate AND-homomorphism, then f is delta-close to either a constant function or an AND function, where delta(epsilon) -> 0 as epsilon -> 0. This improves on a result of Nehama, who proved a similar statement in which delta depends on n. Our theorem implies a strong result on judgement aggregation in computational social choice. In the language of social choice, our result shows that if f is epsilon-close to satisfying judgement aggregation, then it is delta(epsilon)-close to an oligarchy (the name for the AND function in social choice theory). This improves on Nehama's result, in which delta decays polynomially with n. Our result follows from a more general one, in which we characterize approximate solutions to the eigenvalue equation T-f = lambda(g), where T is the downwards noise operator Tf (x) = E-y[f (x boolean AND y)], f is [0, 1]-valued, and. is {0, 1}-valued. We identify all exact solutions to this equation, and show that any approximate solution in which Tf and.. are close is close to an exact solution.

关键词： Property Testing analysis of boolean functions

来源：评论

学校读者我要写书评

暂无评论

Harmonicity and invariance on slices of the boolean cube

引用

PROBABILITY THEORY AND RELATED FIELDS 2019年第3-4期175卷 721-782页

作者： Filmus, Yuval Mossel, Elchanan Technion Israel Inst Technol Dept Comp Sci Haifa Israel MIT Math & IDSS 77 Massachusetts Ave Cambridge MA 02139 USA

In a recent work with Kindler and Wimmer we proved an invariance principle for the slice for low-influence, low-degree harmonicmultilinear polynomials (a polynomial in x1,..., xn is harmonic if it is annihilated by n i=1.. xi). Here we provide an alternative proof for general low-degree harmonicmultilinear polynomials, with no constraints on the influences. We show that any real-valued harmonic multilinear polynomial on the slice whose degree is o(v n) has approximately the same distribution under the slice and cube measures. Our proof is based on ideas and results from the representation theory of Sn, along with a novel decomposition of random increasing paths in the cube in terms of martingales and reverse martingales. While such decompositions have been used in the past for stationary reversibleMarkov chains, our decomposition is applied in a non-stationary non-reversible setup. We also provide simple proofs for some known and some new properties of harmonic functions which are crucial for the proof. Finally, we provide independent simple proofs for the known facts that (1) one cannot distinguish between the slice and the cube based on functions of o(n) coordinates and (2) boolean symmetric functions on the cube cannot be approximated under the uniform measure by functions whose sum of influences is o(root n).

关键词： analysis of boolean functions Invariance principle Johnson scheme Slice

来源：评论

学校读者我要写书评

暂无评论

Noise Sensitivity on the p-Biased Hypercube 60

Noise Sensitivity on the p-Biased Hypercube

引用

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

作者： Lifshitz, Noam Minzer, Dor Hebrew Univ Jerusalem Einstein Inst Math Jerusalem Israel Inst Adv Study Olden Lane Princeton NJ 08540 USA

ISBN: (纸本)9781728149523

The noise sensitivity of a boolean function measures how susceptible the value of f on a typical input x to a slight perturbation of the bits of x: it is the probability f (x) and f (y) are different when x is a uniformly chosen n-bit boolean string, and y is formed by flipping each bit of x with small probability epsilon. The noise sensitivity of a function is a key concept with applications to combinatorics, complexity theory, learning theory, percolation theory and more. In this paper, we investigate noise sensitivity on the p-biased hypercube, extending the theory for polynomially small p. Specifically, we give sufficient conditions for monotone functions with large groups of symmetries to be noise sensitive (which in some cases are also necessary). As an application, we show that the 2-SAT function is noise sensitive around its critical probability. En route, we study biased versions of the invariance principle for monotone functions and give p-biased versions of Bourgain's tail theorem and the Majority is Stablest theorem, showing that in this case the correct analog of "small low degree influences" is lack of correlation with constant width DNF formulas.

关键词： analysis of boolean functions Noise Sensitivity Graph Properties

来源：评论

学校读者我要写书评

暂无评论

Invariance Principle on the Slice

引用

ACM TRANSACTIONS ON COMPUTATION THEORY 2018年第3期10卷 11-11页

作者： Filmus, Yuval Kindler, Guy Mossel, Elchanan Wimmer, Karl Technion Israel Inst Technol Comp Sci Dept Haifa Israel Hebrew Univ Jerusalem Sch Comp Sci & Engn Jerusalem Israel MIT Inst Data Syst & Soc Math 77 Massachusetts Ave Cambridge MA 02139 USA Duquesne Univ Dept Math & Comp Sci Pittsburgh PA 15219 USA

The non-linear invariance principle of Mossel, O'Donnell, and Oleszkiewicz establishes that if f (x(1),...,x(n)) is a multilinear low-degree polynomial with low influences, then the distribution of f(B-1,...,B-n) is close (in various senses) to the distribution of f (G(1),...,G(n)), where B-i is an element of(R) {-1, 1) are independent Bernoulli random variables and G(i) similar to N(0, 1) are independent standard Gaussians. The invariance principle has seen many applications in theoretical computer science, including the Majority is Stablest conjecture, which shows that the Goemans-Williamson algoritlun for MAX-CUT is optimal under the Unique Games Conjecture. More generally, MOO's invariance principle works for any two vectors of hypercontractive random variables (X-1,...,X-n), (y(1),...,y(n)) such that (i) Matching moments: X-i and y(i) have matching first and second moments and (ii) Independence: the variables X-i,...,X-n are independent, as are y(1),...,y(n). The independence condition is crucial to the proof of the theorem, yet in some cases we would like to use distributions (X-1. X-n) in which the individual coordinates are not independent. A common example is the uniform distribution on the slice ([n](k)) Which consists of all vectors (x(1)....,x(n)) is an element of{0,1}(n) with Hamming weight k. The slice shows up in theoretical computer science (hardness amplification, direct sum testing), extremal combinatorics (ErdOs-Ko-Rado theorems), and coding theory (in the guise of the Johnson association scheme). Our main result is art invariance principle in which (X-1,...,X-n) is the uniform distribution on a slice ([n](pn)) and (y(1),...,y(n)) consists either of it independent Ber(p) random variables, or f it independent N(p,p(1 - p)) random variables. As applications, we prove a version of Majority is Stablest for functions on the slice, a version of Bourgain's tail theorem, a version of the Kindler Safra stnictural theorem, and a stability version of the t-i

关键词： analysis of boolean functions invariance principle slice Johnson scheme

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：