Sensitivity, affine transforms and quantum communication complexity

DOI10.1016/j.tcs.2020.05.048zbMath1453.68084arXiv1808.10191OpenAlexW2964545243MaRDI QIDQ5918933

M. N. Jayalal Sarma, Krishnamoorthy Dinesh

Publication date: 1 September 2020

Published in: Theoretical Computer Science, Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1808.10191

zbMATH Keywords

sensitivityalternationaffine transformsquantum communication complexity

Mathematics Subject Classification ID

Boolean functions (06E30) Quantum algorithms and complexity in the theory of computing (68Q12) Communication complexity, information complexity (68Q11)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the parity complexity measures of Boolean functions
• On the degree of Boolean functions as real polynomials
• Complexity measures and decision tree complexity: a survey.
• Sensitivity vs. block sensitivity of Boolean functions
• Induced subgraphs of hypercubes and a proof of the sensitivity conjecture
• Alternation, sparsity and sensitivity: bounds and exponential gaps
• Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
• CREW PRAM<scp>s</scp> and Decision Trees
• Spectral analysis of Boolean functions as a graph eigenvalue problem
• Quantum communication complexity of symmetric predicates
• Sensitivity Conjecture and Log-rank Conjecture for functions with small alternating numbers
• Analysis of Boolean Functions
• Lower Bounds for Quantum Communication Complexity
• Testing Fourier Dimensionality and Sparsity

This page was built for publication: Sensitivity, affine transforms and quantum communication complexity