0000000001037664

AUTHOR

Mohammad Bavarian

showing 3 related works from this author

Tighter Relations between Sensitivity and Other Complexity Measures

2014

The sensitivity conjecture of Nisan and Szegedy [12] asks whether the maximum sensitivity of a Boolean function is polynomially related to the other major complexity measures of Boolean functions. Despite major advances in analysis of Boolean functions in the past decade, the problem remains wide open with no positive result toward the conjecture since the work of Kenyon and Kutin from 2004 [11].

CombinatoricsComplexity indexDiscrete mathematicsConjecture010201 computation theory & mathematics0202 electrical engineering electronic engineering information engineering020201 artificial intelligence & image processing0102 computer and information sciences02 engineering and technologySensitivity (control systems)Boolean function01 natural sciencesMathematics
researchProduct

Weak Parity

2013

We study the query complexity of Weak Parity: the problem of computing the parity of an n-bit input string, where one only has to succeed on a 1/2 + ε fraction of input strings, but must do so with high probability on those inputs where one does succeed. It is well-known that n randomized queries and n/2 quantum queries are needed to compute parity on all inputs. But surprisingly, we give a randomized algorithm for Weak Parity that makes only O(n/log[superscript 0.246](1/ε)) queries, as well as a quantum algorithm that makes O(n/√log(1/ε)) queries. We also prove a lower bound of Ω(n/log(1/ε)) in both cases, as well as lower bounds of Ω(logn) in the randomized case and Ω(√logn) in the quantu…

FOS: Computer and information sciencesComputer Science - Computational ComplexityQuantum PhysicsTheoryofComputation_GENERALFOS: Physical sciencesComputational Complexity (cs.CC)Quantum Physics (quant-ph)
researchProduct

Tighter Relations Between Sensitivity and Other Complexity Measures

2014

Sensitivity conjecture is a longstanding and fundamental open problem in the area of complexity measures of Boolean functions and decision tree complexity. The conjecture postulates that the maximum sensitivity of a Boolean function is polynomially related to other major complexity measures. Despite much attention to the problem and major advances in analysis of Boolean functions in the past decade, the problem remains wide open with no positive result toward the conjecture since the work of Kenyon and Kutin from 2004. In this work, we present new upper bounds for various complexity measures in terms of sensitivity improving the bounds provided by Kenyon and Kutin. Specifically, we show tha…

FOS: Computer and information sciencesComputer Science - Computational ComplexityComputational Complexity (cs.CC)
researchProduct