Karthikeya Polisetty

collaborators

2 papers

cs.CC2026

Bounds for Hardness Condensation in the Query Model

Chandrima Kayal, Rajat Mittal, Sai Soumya Nalli +4

For any Boolean function $f : {0, 1}^{n} \to {0, 1}$ with a complexity measure having value $k ≪ n$ , is it possible to restrict the function $f$ to $I^ (k)$ variables while keeping…

cs.CC2026

On Condensation of Block Sensitivity, Certificate Complexity and the $AND$ (and $OR$ ) Decision Tree Complexity

Sai Soumya Nalli, Karthikeya Polisetty, Jayalal Sarma

Given an $n$ -bit Boolean function with a complexity measure (such as block sensitivity, query complexity, etc.) $M (f) = k$ , the hardness condensation question asks whether $f$ can…

Bounds for Hardness Condensation in the Query Model

On Condensation of Block Sensitivity, Certificate Complexity and the AND (and OR) Decision Tree Complexity

On Condensation of Block Sensitivity, Certificate Complexity and the $AND$ (and $OR$ ) Decision Tree Complexity