Properties and applications of boolean function composition

DOI10.1145/2422436.2422485zbMath1361.68094OpenAlexW2014377018MaRDI QIDQ2986892

Avishay Tal

Publication date: 16 May 2017

Published in: Proceedings of the 4th conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2422436.2422485

zbMATH Keywords

Boolean functionsblock sensitivitydecision tree complexitycertificate complexity

Mathematics Subject Classification ID

Related Items (19)

Low-Sensitivity Functions from Unambiguous Certificates. ⋮ Alternation, sparsity and sensitivity: bounds and exponential gaps ⋮ All Classical Adversary Methods are Equivalent for Total Functions ⋮ Composition limits and separating examples for some Boolean function complexity measures ⋮ Unnamed Item ⋮ Unnamed Item ⋮ LOW-DEGREE BOOLEAN FUNCTIONS ON , WITH AN APPLICATION TO ISOPERIMETRY ⋮ On block sensitivity and fractional block sensitivity ⋮ An asymptotically tight bound on the number of relevant variables in a bounded degree Boolean function ⋮ Unnamed Item ⋮ Quadratically tight relations for randomized query complexity ⋮ Unnamed Item ⋮ On derandomized composition of Boolean functions ⋮ Unnamed Item ⋮ Unnamed Item ⋮ New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity ⋮ Induced subgraphs of hypercubes and a proof of the sensitivity conjecture ⋮ A Composition Theorem for Randomized Query Complexity ⋮ On separation between the degree of a Boolean function and the block sensitivity

Cites Work

• Teachability in computational learning
• Measuring teachability using variants of the teaching dimension
• Teaching a smarter learner.
• Occam's razor
• Pseudorandom generators for space-bounded computation
• On the power of inductive inference from good examples
• A model of interactive teaching
• Learning from different teachers
• On the limits of efficient teachability
• In search of an easy witness: Exponential time vs. probabilistic polynomial time.
• On the complexity of teaching
• On specifying Boolean functions by labelled examples
• Recent Developments in Algorithmic Teaching
• A theory of the learnable
• Teaching Randomized Learners
• Algorithmic Learning Theory
• A theory of goal-oriented communication
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Properties and applications of boolean function composition