Instance complexity of symmetric Boolean functions is completely characterized with only Parity and complement at value 1; Greater-Than and Odd-Max-Bit have constant IC while QC/C_min is linear.
Lecture Notes on Evasiveness of Graph Properties
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
This report presents notes from the first eight lectures of the class Many Models of Complexity taught by Laszlo Lovasz at Princeton University in the fall of 1990. The topic is evasiveness of graph properties: given a graph property, how many edges of the graph an algorithm must check in the worst case before it knows whether the property holds.
fields
cs.CC 1years
2023 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
Instance complexity of Boolean functions
Instance complexity of symmetric Boolean functions is completely characterized with only Parity and complement at value 1; Greater-Than and Odd-Max-Bit have constant IC while QC/C_min is linear.