- Project Year:
2019
- REU Student (s):
Shoshana Simons | Brown University RI
- Student 1 Institution:
Brown University
- Project Mentor:
Robert Robere
- Project Mentor Area:
DIMACS
- Project Abstract:
In Razborov's 1995 paper "Unprovability of Lower Bounds on Circuit Size in Certain Fragments of Bounded Arithmetic", we are told that a certain connection exists between communication complexity and circuit complexity: we are told that if we have a DAG-protocol of size S for the monotone mKW game of f, then there exists a monotone fanout circuit of size S for f, and vice versa. In this work, we begin by discussing a restriction we must place on DAG-protocols for the first direction of this claim to be true; we call this restriction being dead leaf free. We then explore protocols that have what we call reducibility at merges, and we explore what a protocol having reducibility at merges can tell us about the communication problem underlying the protocol. We then think about the relationship between protocols that have reducibility at merges and protocols that are dead leaf free, and we introduce a few open problems about this relationship -some computational in flavor, some combinatorial. Finally, we introduce a new kind of protocol called tie breaking protocols, and we show that tie breaking protocols that are dead leaf free and what we call fair characterize monotone comparator circuits. We end by discussing how we anticipate this protocol can be useful to finding a separation between monotone formulas and monotone comparator circuits.
