boofun.analysis.communication_complexity

Communication Complexity Analysis.

This module provides tools for analyzing the communication complexity of Boolean functions, including: - Deterministic communication complexity D(f) - Randomized communication complexity R(f) - Partition number and fooling sets - Log-rank bounds - Information complexity

References: - Kushilevitz & Nisan, “Communication Complexity” - O’Donnell, “Analysis of Boolean Functions”, Chapter 6

Functions

`cc_disjointness`(n)	Communication complexity of disjointness function.
`cc_equality`(n)	Communication complexity of equality function.
`cc_inner_product`(n)	Communication complexity of inner product function.
`deterministic_cc`(f)	Analyze deterministic communication complexity.
`discrepancy`(f)	Compute the discrepancy of a Boolean function.
`fooling_set_bound`(f)	Compute fooling set lower bound on communication complexity.
`get_communication_matrix`(f)	Build the communication matrix M_f for a Boolean function.
`log_rank_bound`(f)	Compute the log-rank lower bound on communication complexity.
`rectangle_partition_bound`(f[, max_iterations])	Estimate partition number (number of monochromatic rectangles needed).

Classes

`CommunicationComplexityProfile`(f)	Complete communication complexity analysis.
`CommunicationMatrix`(f)	Represents and analyzes the communication matrix of a Boolean function.

boofun.analysis.communication_complexity.deterministic_cc(f: BooleanFunction) → Dict[str, Any][source]

Analyze deterministic communication complexity.

Computes multiple bounds: - Log-rank lower bound - Fooling set lower bound - Rectangle partition upper bound

Parameters:: f – Boolean function
Returns:: Dictionary with bounds and analysis

boofun.analysis.communication_complexity.log_rank_bound(f: BooleanFunction) → Tuple[int, float][source]

Compute the log-rank lower bound on communication complexity.

D(f) ≥ log₂(rank(M_f))

This is a fundamental lower bound: any deterministic protocol must exchange at least log₂(rank(M_f)) bits.

Parameters:: f – Boolean function
Returns:: Tuple of (rank, log_rank_lower_bound)

boofun.analysis.communication_complexity.fooling_set_bound(f: BooleanFunction) → Tuple[int, float][source]

Compute fooling set lower bound on communication complexity.

A fooling set is a set of input pairs {(x₁,y₁), …, (x_k,y_k)} such that: - All f(x_i, y_i) = b for some fixed b - For i ≠ j: f(x_i, y_j) ≠ b or f(x_j, y_i) ≠ b

D(f) ≥ log₂|fooling set|

Parameters:: f – Boolean function
Returns:: Tuple of (fooling_set_size, lower_bound)

boofun.analysis.communication_complexity.rectangle_partition_bound(f: BooleanFunction, max_iterations: int = 1000) → Tuple[int, float][source]

Estimate partition number (number of monochromatic rectangles needed).

The partition number C(f) = min number of monochromatic rectangles needed to partition the input space.

D(f) ≤ log₂(C(f)) + 1

This provides an upper bound on communication complexity.

Parameters:

f – Boolean function
max_iterations – Maximum iterations for greedy partition

Returns:

Tuple of (partition_size, upper_bound)

boofun.analysis.communication_complexity.discrepancy(f: BooleanFunction) → float[source]

Compute the discrepancy of a Boolean function.

Discrepancy measures how “balanced” the function is over rectangles. Low discrepancy implies high randomized communication complexity.

disc(f) = max over rectangles R of |Pr[f=1 on R] - 1/2|

Parameters:: f – Boolean function
Returns:: Discrepancy value

class boofun.analysis.communication_complexity.CommunicationMatrix(f: BooleanFunction)[source]

Represents and analyzes the communication matrix of a Boolean function.

__init__(f: BooleanFunction)[source]

Initialize with Boolean function.

Parameters:: f – Boolean function

property matrix: ndarray: Get the communication matrix (computed lazily).

property rank: int: Get matrix rank.

property singular_values: ndarray: Get singular values.

density() → float[source]: Fraction of 1s in matrix.

spectral_norm() → float[source]: Get largest singular value.

nuclear_norm() → float[source]: Get sum of singular values (nuclear norm).

visualize() → str[source]: Get ASCII visualization of matrix.

summary() → str[source]: Get summary of matrix properties.

class boofun.analysis.communication_complexity.CommunicationComplexityProfile(f: BooleanFunction)[source]

Complete communication complexity analysis.

__init__(f: BooleanFunction)[source]

Initialize profile.

Parameters:: f – Boolean function

compute() → Dict[str, Any][source]: Compute full analysis.

summary() → str[source]: Get summary string.