Advanced Branching Programs: Time-Space Tradeoffs and Form Structures

Branching Programs Part 2 Paul Beame University of Washington

Outline 1. Branching program basics 2. Space (size) lower bounds 3. Multi-output functions Time-Space tradeoff lower bounds for general BPs 4. Single-output functions Restricted classes of BPs OBDDs, Read-once (FBDDs), Oblivious, Read-k Lower bound methods for restricted classes Lower bound methods for general BPs Applying tradeoffs: BPs and static data structures 5. Multi-output functions using single-output techniques Lower bound for encoding good codes

Time-Space Tradeoffs for Single-Output Functions

Obtaining Time-Space Tradeoffs First see how to analyze BPs of special forms...

Limited Branching Program Forms Structure-based Time-Based Read-Once On every path through the BP each variable is queried at most once e.g. Parity BP Read-? ? On every path through the BP each variable is queried at most ? ? times Time-Bounded Every path in the BP has length at most ? = ?? Oblivious For each BP level, all the nodes on that level have the same variable name e.g. Parity BP

Oblivious Read-Once BPs (OBDDs) 10,000 s of papers in formal verification using OBDDs as format for Boolean functions Q: Why so successful? A1: OBDDs for some natural functions are small A2: OBDDs have the good properties of finite automata Oblivious Read-Once ? ? BP levels labelled by vars ? ??(1 An Oblivious Read-Once BP with ordering ? is the diagram of a DFA for ??? ?={? ?? ?(1 Good properties for fixed order ? : Unique canonical form and minimization algorithm Closure algorithms under , and other operations (1) ),...,? ??( (? ?) )for some 1-1 ?: :[? ?] [? ?] {0,1}? ? (1) )...? ?? ?( (? ?) )| ?(? ?1 1, ,...,? ?? ?)=1} )=1} {0,1}

Oblivious Read-Once BP/OBDD DFA ?? ? ? ?? ?? ? ? ? ? ?? ?? ? ? ? ? ?? ?? ? ? ? ? 0 1 ??????(??,??,??,??)

Order Matters for OBDDs Defn:????? ??, ,??,??, ,?? = ? ? = ? With OBDD order ??, ,??,??, ,?? After level ?, OBDD needs ??nodes to remember ? in order to check if ? = ? With OBDD order ??,??, ,??,??only ?(?) size ? ? ? ?? ?? ? ? ? ? ?? ?? ? ? ?? ?? ?? 1 ? ? ? ? ? ? ?? ?? ?? ? ? ? ?? ?? ?? ???,? ???,? ?,? ?,? 0

Communication Complexity Input ? ? Input ? ? 010 11 0 Bob Alice ?(?,?) ?(?) = # of bits Alice and Bob need to exchange to compute ?on? ?

1-way Communication Complexity Input ? ? Input ? ? 010 ?(?,?) Bob Alice ??(?)= # of bits Alice needs to send to Bob for him to compute ?on? ? ??(?)=# of bits for ? rounds

Communication Complexity and OBDD size Theorem: OBDD size of ? with order ? for ? = ? ? , ,? ? and ? = {? is at least ???(??). ? ? ?+ ? , ,? ? } 1 0 ?? ? ?? ? ?? ? ??? ??? ?+? ?? ? ??? ? ? Proof: Alice could send the name of a node at level ? ? .

Proving OBDD Lower Bounds Corollary: OBDD size of ? is exponential in ????? ? ?= min? ??(??). ? The value ????? party communication complexity of ?. It depends only on the partition of the input, not the order. For many simple functions it is known that ????? these functions we get exponential size lower bounds. E.g., Shifted Equality: On input ?0 0,...,??-1 1,?0 0,...,??-1,?, Is ??=?(?+?) mod ? for all ?? [Lipton-Sedgewick 1981] Hidden Weighted Bit: On input ?1,...,?? output ?|?| where |?| is the Hamming weight of ?[Bryant 1986] Middle bit of ?-bit integer multiplication [Bryant 1991] ? is called the best partition 1-way two- ? is ? ? .For

Proving OBDD Lower Bounds Communication complexity-based methods applicable to data stream space lower bounds also apply to yield OBDD size lower bounds: 1-way Number-In-Hand (NIH) multiparty communication complexity ? players instead of just Alice and Bob Each player has sole access to ?/? input bits Players communicate via a shared blackboard (or sequentially) Can sometimes yield larger lower bounds

Limited Branching Program Forms Structure-based Time-Based Read-Once On every path through the BP each variable is queried at most once e.g. Parity BP Read-? ? On every path through the BP each variable is queried at most ? ? times Time-Bounded Every path in the BP has length at most ? = ?? Oblivious For each BP level, all the nodes on that level have the same variable name e.g. Parity BP

Read-once BPs/FBDDs Free Binary Decision Diagrams/Read-once BPs relax the strict input order of OBDDs Different paths in the BP may have different orders No input bit is read more than once on any path: length = ?. FBDDs are not canonical and combination of FBDDs is only convenient if their structures are the same Randomized equivalence test for FBDDs Interpret them as computing polynomials Applying polynomial identity testing techniques.

Limitations of Read-Once BPs/FBDDs Need ?? ? size for Read-Once BPs/FBDDs to compute, e.g. Middle bit of ?-bit integer multiplication [Bollig-Woelfel 2001] Whether an ?x ? binary matrix is a permutation matrix: one 1 in each row and each column Rows and Columns are competing for the order [Krause 1988] Simplest hard function for which bound is known ?,?=? (????? ?????) [B-Li-Roy-Suciu 2015] ?

Lower Bound Techniques Several techniques, e.g. ? is ?-mixed iff for every subset ? of ? input variables, the ?? assignments to ? lead to different subfunctions of ? ?-mixed functions require FBDD size ?? ? Fixed distance frontier cut-and-paste Analyze density of paths to intermediate nodes at fixed distance from root and from them to the sink. Adaptive frontier expansion: Start with the root and follow branches in BP maintaining tree of distinct subfunctions

Reference An excellent reference that presents the major results as of 2000, and connects BDDs and BPs and their many variants is: Ingo Wegener: Branching Programs and Binary Decision Diagrams. SIAM 2000, ISBN 0-89871-458-3

Limited Branching Program Forms Structure-based Time-Based Read-Once On every path through the BP each variable is queried at most once e.g. Parity BP Read-? ? On every path through the BP each variable is queried at most ? ? times Time-Bounded Every path in the BP has length at most ? = ?? Oblivious For each BP level, all the nodes on that level have the same variable name e.g. Parity BP

Oblivious Branching Programs Each oblivious BP has a sequence ?of variables queried. ??,??,???,??,??,??,???,??,???,???,??,??,???, ,?? Variables can appear more than once in the sequence No restriction on the variable order Analysis techniques are based on general best- partition communication complexity Two party [Alon-Maass 1988] Multi-party Number-On-Forehead (NOF) [Chandra-Furst-Lipton 1983] [Babai-Nisan-Szegedy 1992]

Oblivious BPs and Communication Complexity 1 0 ?? ?? ??? ?? ?? ?? ?? ?? ??? ??? ?? ?? ??? ?? ?? ?? ?? ?? ?? ??? ??? ?? ?? ?? ?? ?? ??? ?? ?? ?? ?? ?? ??? ??? ?? ?? ??? ?? ?? ?? ?? ?? ?? ??? ??? ?? ?? ?? ?= Split the BP (or ?) into ? layers (resp. segments) Assign each layer/segment to either Alice or Bob Each player receives part of the input for variables read in their layers Some parts of the input are seen by both players Say ? = # of private variables per player On input ?, players alternate communicating the names of the elements of trace( trace(?) ) where layer assignment switches. # of rounds ?= # alternations of assignment At most ? ? ? ? bits total

Oblivious BPs and Communication Complexity 1 0 ?? ?? ??? ?? ?? ?? ?? ?? ??? ??? ?? ?? ??? ?? ?? ?? ?? ?? ?? ??? ??? ?? ?? ?? ?= Split the BP (or ?) into ? layers (resp. segments) ? = # of private variables per player On input ?, players alternate communicating the names of the elements of trace( trace(?) ) where layer assignment switches. # of rounds ? = # alternations of assignment At most ? ? ? ? bits total So... for this split of the private variables and every value ? for the shared part of the input, the ?-round communication complexity of ?? (?with ?fixed) satisfies ??(??) ? ?. ? ??(??)/?

Hardness Property and a Hard Function Best partition property yielding good bounds: splits of ? input vars to Alice and ? input vars to Bob an assignment to the rest s.t. communication complexity is large: Recall???,?? ??,??, ,?? = 1 1 iff all ?? are different. For a multiway (?2 2-way) BP for ???,?? Alice and Bob each get ? numbers We assign distinct values to the rest Resulting function for Alice & Bob is SetDisjointness ?(?) communication complexity lower bound for unlimited rounds is well known SetDisjointness

Good Strategies for Assigning Layers 1 0 ?? ?? ??? ?? ?? ?? ?? ?? ??? ??? ?? ?? ??? ?? ?? ?? ?? ?? ?? ??? ??? ?? ?? ?? ?= Assign each layer/segment to either Alice or Bob for ? = ?? Goal: maximize # of variables per player ?, while minimizing # of rounds ? ?. Lower bound ? ?(?)/? 3 constructions known, one deterministic, two randomized 1. Length of layers depends on ? [Alon-Maass 1988] 2. Flip an independent coin for each layer: ?=?/2 2? ?+1 =8?2 22 2? equal length layers [Borodin-Razborov-Smolensky 1989, B-Jayram-Saks 2001] 3. Use 4 4?2 equal layers. Give a random subset of 2 2? of them to Bob. ? ?/(6 6?)2 2?, ?=4 4?2 2, ?=4 4?+1 1 [Okol nishnikova 1989, Ajtai 2001] +1, ? ?=8

BRS Strategy for Assigning Layers Flip an independent coin for each layer of a length ?=?? oblivious BP split into ? equal-length layers Each input variable ?? appears ? times on average If ?? appears exactly ? times then Pr[all ? layers contain ?? are assigned to Alice] 1 1/2 2? Without assumption, E[# vars assigned only to Alice] ?/2 2? An uneven distribution has larger expected value But the assignments are correlated within each layer Value ?=8 8?2 22 2?keeps correlation small Alon and Maass show that this is essentially best ? possible

Oblivious BP Lower Bound for ???,?? We have ? = ?? ? =?/2 2? ?+ +1 ? ? = 8 Therefore, ? ??/ (?2 22 22 2?) for some constant ? i.e. ? ?/2 2? ?or 2 2? ? ?/? Taking logs we get ? ? log2(?/?) Since ?=?/? we get ?=?(? log(?/?)) 1 # of variables per player = 8?2 22 2? # of rounds ? ?(?)/? With more care can get ?=?(? log((?log ?)/?))

Even Larger Oblivious BP Lower Bounds Multiparty Number-On-Forehead Communication Complexity [Chandra-Furst-Lipton 1983] Each input variable is seen by all but one of ?players Layer assignment indicates which player cannot simulate the layer More variables remain: ?=?/??/? [Babai-Nisan-Szegedy 89] prove ?(?/2 2?) lower bounds Using ?=?(log ?) players, get ?=?(? log2 2 (?/?)) e.g. PointerJumping PointerJumping: Is there a path of [B-Vee 2002] pointers from 1 1 to ?? Time ? and space ?(log ?) for general BPs

Open Problems for Oblivious BPs Prove any lower bound for an explicit single-output function that holds for time ?= ? log?(1) ? or even ?=?(? log2 ?). Babai, Nisan, and Szegedy s?=?(? log2 2(?/?)) lower bound is the largest lower bound known for any explicit single-output function. Has not been improved in > 25 years Improvement in # of players for NOF communication complexity is a notorious hard problem that would also give new circuit lower bounds Prove ?=?(? log2 2 (?/?)) lower bound for a wider range of natural functions