Lifting to randomized parity decision trees

DOI10.4230/LIPICS.APPROX/RANDOM.2025.55MaRDI QIDQ7346888zbMATH OpenFDO

Authors Farzan Byramji, Russell Impagliazzo

Publication date 11 September 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.APPROX/RANDOM.2025.55

Mathematics Subject Classification ID

Randomized algorithms (68W20) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Cites work

• A composition theorem for decision tree complexity
• A composition theorem for randomized query complexity
• A new minimax theorem for randomized algorithms (extended abstract)
• Communication lower bounds via critical block sensitivity
• Complexity measures and decision tree complexity: a survey.
• Deterministic communication vs. partition number
• Exponential separation between powers of regular and general resolution over parities
• scientific article; zbMATH DE number 6913819 (Why is no real title available?)
• scientific article; zbMATH DE number 1445296 (Why is no real title available?)
• scientific article; zbMATH DE number 7829336 (Why is no real title available?)
• scientific article; zbMATH DE number 7789149 (Why is no real title available?)
• Title not available (Why is no real title available?)
• Title not available (Why is no real title available?)
• Improved quantum query upper bounds based on classical decision trees
• Learning decision trees from random examples
• Lifting dichotomies
• Lifting Nullstellensatz to monotone span programs over any field
• Lifting to parity decision trees via stifling
• Monotone circuit lower bounds from resolution
• On (simple) decision tree rank
• On disperser/lifting properties of the index and inner-product functions
• On the composition of randomized query complexity and approximate degree
• Optimal direct sum results for deterministic and randomized decision tree complexity
• Properties and applications of Boolean function composition
• Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
• Query-to-communication lifting for BPP
• Query-to-communication lifting using low-discrepancy gadgets
• Randomised composition and small-bias minimax
• Randomized communication versus partition number
• Randomized query composition and product distributions
• Resolution over linear equations modulo two
• Separation of the monotone NC hierarchy
• Separations in query complexity using cheat sheets
• Simulation theorems via pseudo-random properties
• The depth of resolution proofs
• The power of many samples in query complexity

This page was built for publication: Lifting to randomized parity decision trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7346888)