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

On Parity Decision Trees for Fourier-sparse boolean functions

ACM TRANSACTIONS ON COMPUTATION THEORY 2024年第2期16卷 1-26页

作者： Mande, Nikhil S. Sanyal, Swagato Univ Liverpool Ashton BldgAshton St Liverpool L69 3BX Merseyside England Indian Inst Technol Kharagpur Dept Comp Sci & Engn Kharagpur W Bengal India

We study parity decision trees for boolean functions. The motivation of our study is the log-rank conjecture for XOR functions and its connection to Fourier analysis and parity decision tree complexity. Our contributions are as follows: Let f : F-2(n) -> {-1, 1} be a boolean function with Fourier support S and Fourier sparsity k. - We prove via the probabilistic method that there exists a parity decision tree of depth O(root k) that computes f. This matches the previously best-known upper bound on the parity decision tree complexity of boolean functions (Tsang, Wong, Xie, and Zhang, FOCS'13). Moreover, while previous constructions (Tsang et al., FOCS 2013, Shpilka, Tal, and Volk, Comput. Complex. 2017) build the trees by carefully choosing the parities to be queried in each step, our proof shows that a naive sampling of the parities suffices. - We generalize the above result by showing that if the Fourier spectra of boolean functions satisfy a natural "folding property," then the above proof can be adapted to establish existence of a tree of complexity polynomially smaller than O(root k). More concretely, the folding property we consider is that for most distinct gamma, delta in S, there are at least a polynomial (in k) number of pairs {alpha, beta} of parities in S such that alpha + beta = gamma + delta. We pose a question in this regard that, if answered in the positive, implies that the communication complexity of an XOR function is bounded above by the fourth root of the rank of its communication matrix, improving upon the previously known upper bound of square root of rank (Tsang et al., FOCS'13, Lovett, J. ACM. 2016). - Motivated by the above, we present some structural results about the Fourier spectra of boolean functions. It can be shown by elementary techniques that for any boolean function f and all {alpha, beta} in ((S)(2)), there exists another pair {gamma, delta} in ((S)(2)) such that alpha + beta = gamma + delta. One can view this as a "trivial" foldi

关键词： Parity decision trees log-rank conjecture analysis of boolean functions communication complexity

来源：评论

学校读者我要写书评

暂无评论

Influences in Mixing Measures 2024

Influences in Mixing Measures

引用

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

作者： Koehler, Frederic Lifshitz, Noam Minzer, Dor Mossel, Elchanan Univ Chicago Chicago IL USA Hebrew Univ Jerusalem Jerusalem Israel MIT Cambridge MA 02139 USA

ISBN: (纸本)9798400703836

The theory of influences in product measures has profound applications in theoretical computer science, combinatorics, and discrete probability. This deep theory is intimately connected to functional inequalities and to the Fourier analysis of discrete groups. Originally, influences of functions were motivated by the study of social choice theory, wherein a boolean function represents a voting scheme, its inputs represent the votes, and its output represents the outcome of the elections. Thus, product measures represent a scenario in which the votes of the parties are randomly and independently distributed, which is often far from the truth in real-life scenarios. We begin to develop the theory of influences for more general measures under mixing or spectral independence conditions. More specifically, we prove analogues of the KKL and Talagrand influence theorems for Markov Random Fields on bounded degree graphs when the Glauber dynamics mix rapidly. We thus resolve a long standing challenge, stated for example by Kalai and Safra (2005). We show how some of the original applications of the theory of in terms of voting and coalitions extend to these general dependent measures. Our results thus shed light both on voting with correlated voters and on the behavior of general functions of Markov Random Fields (also called "spin-systems") where the Glauber dynamics mixes rapidly.

关键词： analysis of boolean functions Influences of Variables Non-product Measures

来源：评论

学校读者我要写书评

暂无评论

Randomized Query Composition and Product Distributions 41

Randomized Query Composition and Product Distributions

引用

41st International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Sanyal, Swagato Indian Inst Technol Kharagpur Dept Comp Sci & Engn Kharagpur India

ISBN: (纸本)9783959773119

Let RE denote randomized query complexity for error probability epsilon, and R := R-1/3. In this work we investigate whether a perfect composition theorem R(f o g(n)) = Omega(R(f) center dot R(g)) holds for a relation f subset of {0,1}(n) x S and a total inner function g: {0,1}(m) -> {0, 1}. Composition theorems of the form R(f o g(n)) = Omega(R(f) center dot M(g)) are known for various measures M. Such measures include the sabotage complexity RS defined by Ben-David and Kothari (ICALP 2015), the max-conflict complexity defined by Gavinsky, Lee, Santha and Sanyal (ICALP 2019), and the linearized complexity measure defined by Ben-David, Blais, Goos and Maystre (FOCS 2022). The above measures are asymptotically non-decreasing in the above order. However, for total boolean functions no asymptotic separation is known between any two of them. Let D-prod denote the maximum distributional query complexity with respect to any product (over variables) distribution. In this work we show that for any total boolean function g, the sabotage complexity RS(g) = (Omega) over tilde (D-prod (g)). This gives the composition theorem R(f o g(n)) = (R(f) center dot D-prod (g)) In light of the minimax theorem which states that R(g) is the maximum distributional complexity of g over any distribution, our result makes progress towards answering the composition question. We prove our result by means of a complexity measure R-epsilon(prod) that we define for total boolean functions. Informally, R-epsilon(prod) (g) is the minimum complexity of any randomized decision tree with unlabelled leaves with the property that, for every product distribution it over the inputs, the average bias of its leaves is at least ((1 - epsilon) - epsilon)/2 = 1/2 - epsilon. It follows by standard arguments R-1/3(prod)(g) = Omega(D-prod (g)). We show that R-1/3(prod) is equivalent to the sabotage complexity up to a logarithmic factor. Ben-David and Kothari asked whether RS(g) = Theta(R(g)) for total functions g. W

关键词： analysis of boolean functions boolean function complexity Decision Tree Randomized query complexity

来源：评论

学校读者我要写书评

暂无评论

A Dense Model Theorem for the boolean Slice 65

A Dense Model Theorem for the Boolean Slice

引用

65th Symposium on Foundations of Computer Science

作者： Kalai, Gil Lifshitz, Noam Minzer, Dor Ziegler, Tamar Hebrew Univ Jerusalem Jerusalem Israel Reichman Univ Herzliyya Israel MIT 77 Massachusetts Ave Cambridge MA 02139 USA

ISBN: (纸本)9798331516758;9798331516741

The (low soundness) linearity testing problem for the middle slice of the boolean cube is as follows. Let epsilon > 0 and f be a function on the middle slice on the boolean cube, such that when choosing a uniformly random quadruple (x, y, z, x circle plus y circle plus z) of vectors of 2n bits with exactly n ones, the probability that f(x circle plus y circle plus z) = f(x) circle plus f(y) circle plus f(z) is at least 1/2 + epsilon. The linearity testing problem, posed by [6], asks whether there must be an actual linear function that agrees with f on 1/2+epsilon' fraction of the inputs, where epsilon' = epsilon'(epsilon) > 0. We solve this problem, showing that f must indeed be correlated with a linear function. To do so, we prove a dense model theorem for the middle slice of the boolean hypercube for Gowers uniformity norms. Specifically, we show that for every k is an element of N, the normalized indicator function of the middle slice of the boolean hypercube {0, 1}(2n) is close in Gowers norm to the normalized indicator function of the union of all slices with weight t = n (mod 2(k-1)). Using our techniques we also give a more general 'low degree test' and a biased rank theorem for the slice.

关键词： Property Testing Dense Model Theorems analysis of boolean functions Gowers' Uniformity Norms

来源：评论

学校读者我要写书评

暂无评论

On the Pauli Spectrum of QAC0 2024

On the Pauli Spectrum of QAC0

引用

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

作者： Nadimpalli, Shivam Parham, Natalie Vasconcelos, Francisca Yuen, Henry Columbia Univ New York NY 10027 USA Univ Calif Berkeley Berkeley CA 94720 USA

ISBN: (纸本)9798400703836

The circuit class QAC(0) was introduced by Moore (1999) as a model for constant depth quantum circuits where the gate set includes many-qubit Toffoli gates. Proving lower bounds against such circuits is a longstanding challenge in quantum circuit complexity;in particular, showing that polynomial-size QAC(0) cannot compute the parity function has remained an open question for over 20 years. In this work, we identify a notion of the Pauli spectrum of QAC(0) circuits, which can be viewed as the quantum analogue of the Fourier spectrum of classical AC(0) circuits. We conjecture that the Pauli spectrum of QAC(0) circuits satisfies low-degree concentration, in analogy to the famous Linial, Mansour, Nisan (LMN) theorem on the low-degree Fourier concentration of AC(0) circuits. If true, this conjecture immediately implies that polynomial-size QAC(0) circuits cannot compute parity. We prove this conjecture for the class of depth-d, polynomial-size QAC(0) circuits with at most n(O(1/d)) auxiliary qubits. We obtain new circuit lower bounds and learning results as applications: this class of circuits cannot correctly compute the n-bit parity function on more than (1/2 + 2-(Omega(n1/d)))-fraction of inputs, and the n-bit majority function on more than (1/2 + O(n(-1/4)))-fraction of inputs. Additionally we show that this class of QAC(0) circuits with limited auxiliary qubits can be learned with quasipolynomial sample complexity, giving the first learning result for QAC(0) circuits. More broadly, our results add evidence that Pauli-analytic techniques can be a powerful tool in studying quantum circuits.

关键词： QAC0 analysis of boolean functions quantum circuit complexity

来源：评论

学校读者我要写书评

暂无评论

Optimal Non-adaptive Tolerant Junta Testing via Local Estimators 2024

Optimal Non-adaptive Tolerant Junta Testing via Local Estima...

引用

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

作者： Nadimpalli, Shivam Patel, Shyamal Columbia Univ New York NY 10027 USA

ISBN: (纸本)9798400703836

We give a non-adaptive algorithm that makes 2((O) over tilde(root klog(1/epsilon 2 - epsilon 1))) queries to a boolean function f:{+/- 1}(n)->{+/- 1} and distinguishes between f being epsilon(1)-close to some k-junta versus epsilon(2)-far from every k-junta. At the heart of our algorithm is a local mean estimation procedure for boolean functions that may be of independent interest. We complement our upper bound with a matching lower bound, improving a recent lower bound obtained by Chen et al. We thus obtain the first tight bounds for a natural property of boolean functions in the tolerant testing model.

关键词： Tolerant property testing juntas analysis of boolean functions local mean estimation

来源：评论

学校读者我要写书评

暂无评论

On Approximability of Satisfiable k-CSPs: IV 2024

On Approximability of Satisfiable k-CSPs: IV

引用

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

作者： Bhangale, Amey Khot, Subhash Minzer, Dor Univ Calif Riverside Dept Comp Sci & Engn Riverside CA 92521 USA NYU Courant Inst Math Sci Dept Comp Sci New York NY USA MIT Cambridge MA USA

ISBN: (纸本)9798400703836

We prove a stability result for general 3-wise correlations over distributions satisfying mild connectivity properties. More concretely, we show that if Sigma,Gamma and phi are alphabets of constant size, and mu is a distribution over Sigma x Gamma x phi satisfying: (1) the probability of each atom is at least Omega(1), (2) mu is pairwise connected, and (3) mu has no Abelian embeddings into (Z,+), then the following holds. Any triplets of 1-bounded functions f: Sigma(n)-> C, g: Gamma(n)-> C, h: phi(n)-> C satisfying vertical bar E-(x,E-y,E-z)similar to mu circle times n [f(x)g(y)h(z)]vertical bar >= epsilon must arise from an Abelian group associated with the distribution mu. More specifically, we show that there is an Abelian group (H,+) of constant size such that for any such f,g and h, the function f (and similarly g and h) is correlated with a function of the form (f)over tilde>(x) = chi(sigma(x(1)), . . . ,sigma(x(n))) L (x), where sigma: Sigma -> H is some map, chi epsilon (H) over cap (circle times n) is a character, and L: Sigma(n)-> C is a low-degree function with bounded 2-norm. En route we prove a few additional results that may be of independent interest, such as an improved direct product theorem, as well as a result we refer to as a restriction inverse theorem about the structure of functions that, under random restrictions, with noticeable probability have significant correlation with a product function. In companion papers, we show applications of our results to the fields of Probabilistically Checkable Proofs, as well as various areas in discrete mathematics such as extremal combinatorics and additive combinatorics.

关键词： PCP analysis of boolean functions Abelian Embeddings

来源：评论

学校读者我要写书评

暂无评论

Quantum and Classical Low-Degree Learning via a Dimension-Free Remez Inequality 15

Quantum and Classical Low-Degree Learning via a Dimension-Fr...

引用

15th Innovations in Theoretical Computer Science Conference (ITCS)

作者： Klein, Ohad Slote, Joseph Volberg, Alexander Zhang, Haonan Hebrew Univ Jerusalem Sch Engn & Comp Sci Jerusalem Israel CALTECH Dept Comp & Math Sci Pasadena CA 91125 USA Michigan State Univ Dept Math Ann Arbor MI 48109 USA Univ Bonn Hausdorff Ctr Math Bonn Germany Univ South Carolina Dept Math Columbia SC 29208 USA

ISBN: (纸本)9783959773096

Recent efforts in analysis of boolean functions aim to extend core results to new spaces, including to the slice ([n,k), the hypergrid [K](n), and noncommutative spaces (matrix algebras). We present here a new way to relate functions on the hypergrid (or products of cyclic groups) to their harmonic extensions over the polytorus. We show the supremum of a function f over products of the cyclic group {exp(2 pi ik/K)} (K)(k=1) controls the supremum of f over the entire polytorus ({z is an element of 1}'), with multiplicative constant C depending on K and deg(f) only. This Remez-type inequality appears to be the first such estimate that is dimension-free (i.e., C does not depend on n). This dimension-free Remez-type inequality removes the main technical barrier to giving 0(log n) sample complexity, polytime algorithms for learning low-degree polynomials on the hypergrid and low-degree observables on level-K qudit systems. In particular, our dimension-free Remez inequality implies new Bohnenblust Hille-type estimates which are central to the learning algorithms and appear unobtainable via standard techniques. Thus we extend to new spaces a recent line of work [10, 13, 23] that gave similarly efficient methods for learning low-degree polynomials on the hypercube and observables on qubits. An additional product of these efforts is a new class of distributions over which arbitrary quantum observables are well-approximated by their low-degree truncations a phenomenon that greatly extends the reach of low-degree learning in quantum science [13].

关键词： analysis of boolean functions Remez Inequality Bohnenblust-Hille Inequality Statistical Learning Theory Qudits

来源：评论

学校读者我要写书评

暂无评论

A strong composition theorem for junta complexity and the boosting of property testers 64

A strong composition theorem for junta complexity and the bo...

引用

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

作者： Blanc, Guy Koch, Caleb Strassle, Carmen Tan, Li-Yang Stanford Univ Stanford CA 94305 USA

ISBN: (纸本)9798350318944

We prove a strong composition theorem for junta complexity and show how such theorems can be used to generically boost the performance of property testers. The epsilon-approximate junta complexity of a function f is the smallest integer r such that f is epsilon-close to a function that depends only on r variables. A strong composition theorem states that if f has large e-approximate junta complexity, then g circle f has even larger epsilon'-approximate junta complexity, even for epsilon' >> epsilon. We develop a fairly complete understanding of this behavior, proving that the junta complexity of g circle f is characterized by that of f along with the multivariate noise sensitivity of g. For the important case of symmetric functions g, we relate their multivariate noise sensitivity to the simpler and well-studied case of univariate noise sensitivity. We then show how strong composition theorems yield boosting algorithms for property testers: with a strong composition theorem for any class of functions, a large-distance tester for that class is immediately upgraded into one for small distances. Combining our contributions yields a booster for junta testers, and with it new implications for junta testing. This is the first boosting-type result in property testing, and we hope that the connection to composition theorems adds compelling motivation to the study of both topics.

关键词： composition theorem junta complexity analysis of boolean functions property testing

来源：评论

学校读者我要写书评

暂无评论

Parallel Repetition for the GHZ Game: Exponential Decay 64

Parallel Repetition for the GHZ Game: Exponential Decay

引用

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

作者： Braverman, Mark Khot, Subhash Minzer, Dor Princeton Univ Princeton NJ 08544 USA New York Univ New York NY USA MIT Cambridge MA 02139 USA

We show that the value of the n-fold repeated GHZ game is at most 2(-Omega)(n), improving upon the polynomial bound established by Holmgren and Raz. Our result is established via a reduction to approximate subgroup ty... 详细信息

ISBN: (纸本)9798350318944

关键词： Parallel Repetition GHZ game Abelian Embeddings analysis of boolean functions Additive Combinatorics

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：