<p>I am not sure if this is very relevant but in <a href="http://link.springer.com/article/10.1007/s00224-013-9469-9" rel="nofollow">Log-Space Algorithms for Paths and Matchings in k-Trees</a> (building on a long history of past work and specifically on <a href="http://www.imsc.res.in/~meena/papers/tocs-arithnc.pdf" rel="nofollow">Arithmetizing classes around NC1 and L</a> by Limaye-Mahajan-Rao) we show how to find recursive balanced separators for a tree in Logspace. This bound may very well be improvable to $\mathsf{NC}^1$ if the input tree is directly given in the string representation.</p>

<p>The basic idea is to represent the tree as a parenthesis expression and find balanced separators for these. Notice that we find leaf separators i.e. subtrees which are balanced w.r.t. number of leaves.</p>

CC BY-SA 3.0
2013-10-23T19:47:14.420Z
2013-10-23T19:47:14.420Z
SamiD
<p>I stumbled upon this question now, many years later. In the interim the following paper has appeared:</p>
<p><a href="https://dl.acm.org/doi/10.1145/3278158" rel="nofollow noreferrer">https://dl.acm.org/doi/10.1145/3278158</a></p>
<p><a href="https://arxiv.org/abs/1704.08705" rel="nofollow noreferrer">https://arxiv.org/abs/1704.08705</a></p>
<p>There the authors do precisely what Kaveh asks for in his question 2: they give a (uniform) TC0 algorithm for balancing, hence obtaining an alternative proof of the main result in Buss '87, as was the original motivation of this question.</p>

CC BY-SA 4.0
2020-10-01T16:50:35.260Z
2020-10-01T17:26:01.567Z
2020-10-01T17:26:01.567Z
Anupam Das
<p>I am looking for references about the complexity of <em>Boolean formula balancing</em> problem. In particular,</p>
<ol>
<li>Was it known that Boolean formulas can be balanced in <span class="math-container">$\mathsf{AC^0}$</span>?</li>
<li>Is there a simple proof of Boolean formula balancing being in <span class="math-container">$\mathsf{AC^0}$</span>?</li>
</ol>
<p>By &quot;simple&quot; I mean a proof simpler than the one I mention below, in particular I am looking for a proof which doesn't depend on Boolean formula evaluation being in <span class="math-container">$\mathsf{NC^1}$</span>.</p>
<hr />
<h3>Background</h3>
<p>Here all mentioned complexity classes are the uniform ones.</p>
<blockquote>
<p><strong>BFB</strong> (Boolean formula balancing):<br />
Given a Boolean formula <span class="math-container">$\varphi$</span>,<br />
Find an equivalent balanced Boolean formula.</p>
</blockquote>
<p>I am interested in the complexity of this problem, in particular simple proofs showing the problem is in <span class="math-container">$\mathsf{AC^0}$</span> (or even <span class="math-container">$\mathsf{TC^0}$</span> or <span class="math-container">$\mathsf{NC^1}$</span>). The common balancing arguments like those based on Spira's lemma apply repeated structural modifications to the formula tree which seem to only give <span class="math-container">$BFB \in \mathsf{NC^2}$</span>.</p>
<p>I have a proof for <span class="math-container">$BFB \in \mathsf{AC^0}$</span>, however the proof is not simple and depends on the proof of <span class="math-container">$BFE \in \mathsf{NC^1}$</span>.</p>
<blockquote>
<p><strong>BFE</strong> (Boolean formula evaluation)<br />
Given a Boolean formula <span class="math-container">$\varphi$</span> and a truth assignment <span class="math-container">$\tau$</span> for variables in <span class="math-container">$\varphi$</span>,<br />
Does <span class="math-container">$\tau$</span> satisfy <span class="math-container">$\varphi$</span> (<span class="math-container">$\tau \vDash \varphi$</span>)?</p>
</blockquote>
<p>It is known from Sam Buss's celebrated result that <em>Boolean formula evaluation</em> (<span class="math-container">$BFE$</span>) can be computed in <span class="math-container">$\mathsf{NC^1} = \mathsf{ALogTime}$</span> (see<a href="http://www.math.ucsd.edu/%7Esbuss/ResearchWeb/Boolean/" rel="noreferrer"> [Buss87]</a> and <a href="http://euclid.ucsd.edu/%7Esbuss/ResearchWeb/Boolean2/" rel="noreferrer"> [BCGR92]</a>).</p>
<p>It follows (quite surprisingly, at least to me) that <em>Boolean formulas balancing</em> (<span class="math-container">$BFB$</span>) is also in <span class="math-container">$\mathsf{NC^1}$</span>:</p>
<p>The idea is that we can hardcode <span class="math-container">$\varphi$</span> in the input gates of <span class="math-container">$BFE$</span> to obtain a formula equivalent to <span class="math-container">$\varphi$</span> and this is a completely syntactic operation computable in <span class="math-container">$\mathsf{AC^0}$</span>. Since <span class="math-container">$BFE$</span> has balanced formulas we obtain a equivalent balanced formula for <span class="math-container">$\varphi$</span>. In other words, the algorithm is:</p>
<p><span class="math-container">$$\ulcorner \varphi \urcorner \mapsto \ulcorner \lambda \vec{p}. Eval(\ulcorner \varphi \urcorner, \vec{p} )\urcorner$$</span></p>
<h3>Motivation</h3>
<p>A simpler argument for <span class="math-container">$BFB$</span> being in <span class="math-container">$\mathsf{AC^0}$</span> (or <span class="math-container">$\mathsf{TC^0}$</span> or even <span class="math-container">$\mathsf{NC^1}$</span>) would give a new simpler proof of <span class="math-container">$BFE \in \mathsf{NC^1}$</span> since it is easy to see that the <em>balanced</em> version of BFE can be solved in <span class="math-container">$\mathsf{NC^1}$</span> and we can compose it with <span class="math-container">$BFB$</span> and the result will be in <span class="math-container">$\mathsf{NC^1}$</span>.</p>
<hr />
<h3>Questions</h3>
<ol>
<li>Was it known that Boolean formulas can be balanced in <span class="math-container">$\mathsf{AC^0}$</span> (<span class="math-container">$BFB\in \mathsf{AC^1}$</span>)?</li>
<li>Is there a simpler argument (e.g. not relying on <span class="math-container">$BFE\in \mathsf{NC^1}$</span>) for <span class="math-container">$BFB\in\mathsf{AC^0}$</span>?</li>
</ol>

CC BY-SA 3.0
2012-12-31T17:24:40.203Z
What definition of "balance" do you use?
Dana Moshkovitz
CC BY-SA 3.0
2013-01-03T08:09:49.577Z
@Dana, we can use something like $Depth < 10\lg Size + 100 $ (i.e. $Depth = O(\lg Size)$ with specific constants). See also Bonnet and Buss's paper "[Size-Depth Tradeoff for Boolean Formulae](http://math.ucsd.edu/~sbuss/ResearchWeb/fmlarestructure/paper.pdf)", 2002.
Kaveh
CC BY-SA 3.0
2013-10-23T20:57:14.150Z
agreed the defn of "balancing" should be made clear. is this similar to the concept of balancing in binary trees? eg ["self balanced trees"](http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree)
vzn
<cc.complexity-theory><ds.algorithms><reference-request><lo.logic><boolean-formulas>
Boolean formula balancing in $\mathsf{AC^0}$
Kaveh
# Boolean formula balancing in $\mathsf{AC^0}$

(Asked by: username_0 on 2012-12-30)

I am looking for references about the complexity of *Boolean formula balancing* problem. In particular,

1. Was it known that Boolean formulas can be balanced in $\mathsf{AC^0}$?
2. Is there a simple proof of Boolean formula balancing being in $\mathsf{AC^0}$?

By "simple" I mean a proof simpler than the one I mention below, in particular I am looking for a proof which doesn't depend on Boolean formula evaluation being in $\mathsf{NC^1}$.

---

### Background

Here all mentioned complexity classes are the uniform ones.

> **BFB** (Boolean formula balancing):  
> Given a Boolean formula $\varphi$,  
> Find an equivalent balanced Boolean formula.

I am interested in the complexity of this problem, in particular simple proofs showing the problem is in $\mathsf{AC^0}$ (or even $\mathsf{TC^0}$ or $\mathsf{NC^1}$). The common balancing arguments like those based on Spira's lemma apply repeated structural modifications to the formula tree which seem to only give $BFB \in \mathsf{NC^2}$.

I have a proof for $BFB \in \mathsf{AC^0}$, however the proof is not simple and depends on the proof of $BFE \in \mathsf{NC^1}$.

> **BFE** (Boolean formula evaluation)  
> Given a Boolean formula $\varphi$ and a truth assignment $\tau$ for variables in $\varphi$,  
> Does $\tau$ satisfy $\varphi$ ($\tau \vDash \varphi$)?

It is known from Sam Buss's celebrated result that *Boolean formula evaluation* ($BFE$) can be computed in $\mathsf{NC^1} = \mathsf{ALogTime}$ (see [[Buss87]](http://www.math.ucsd.edu/%7Esbuss/ResearchWeb/Boolean/) and  [[BCGR92]](http://euclid.ucsd.edu/%7Esbuss/ResearchWeb/Boolean2/)).

It follows (quite surprisingly, at least to me) that *Boolean formulas balancing* ($BFB$) is also in $\mathsf{NC^1}$:

The idea is that we can hardcode $\varphi$ in the input gates of $BFE$ to obtain a formula equivalent to $\varphi$ and this is a completely syntactic operation computable in $\mathsf{AC^0}$. Since $BFE$ has balanced formulas we obtain a equivalent balanced formula for $\varphi$. In other words, the algorithm is:

$$\ulcorner \varphi \urcorner \mapsto \ulcorner \lambda \vec{p}. Eval(\ulcorner \varphi \urcorner, \vec{p} )\urcorner$$

### Motivation

A simpler argument for $BFB$ being in $\mathsf{AC^0}$ (or $\mathsf{TC^0}$ or even $\mathsf{NC^1}$) would give a new simpler proof of $BFE \in \mathsf{NC^1}$ since it is easy to see that the *balanced* version of BFE can be solved in $\mathsf{NC^1}$ and we can compose it with $BFB$ and the result will be in $\mathsf{NC^1}$.

---

### Questions

1. Was it known that Boolean formulas can be balanced in $\mathsf{AC^0}$ ($BFB\in \mathsf{AC^1}$)?
2. Is there a simpler argument (e.g. not relying on $BFE\in \mathsf{NC^1}$) for $BFB\in\mathsf{AC^0}$?

**Tags:** cc.complexity-theory, ds.algorithms, reference-request, lo.logic, boolean-formulas
> **Comments:**
> **username_1**: What definition of "balance" do you use?  
> **username_0**: @Dana, we can use something like $Depth < 10\lg Size + 100 $ (i.e. $Depth = O(\lg Size)$ with specific constants). See also Bonnet and Buss's paper "[Size-Depth Tradeoff for Boolean Formulae](http://math.ucsd.edu/~sbuss/ResearchWeb/fmlarestructure/paper.pdf)", 2002.  
> **username_2**: agreed the defn of "balancing" should be made clear. is this similar to the concept of balancing in binary trees? eg ["self balanced trees"](http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree)  

---

## 2 answers

### Answer by username_3 on 2013-10-23. Score: 3

I am not sure if this is very relevant but in [Log-Space Algorithms for Paths and Matchings in k-Trees](http://link.springer.com/article/10.1007/s00224-013-9469-9) (building on a long history of past work and specifically on [Arithmetizing classes around NC1 and L](http://www.imsc.res.in/~meena/papers/tocs-arithnc.pdf) by Limaye-Mahajan-Rao) we show how to find recursive balanced separators for a tree in Logspace. This bound may very well be improvable to $\mathsf{NC}^1$ if the input tree is directly given in the string representation.

The basic idea is to represent the tree as a parenthesis expression and find balanced separators for these. Notice that we find leaf separators i.e. subtrees which are balanced w.r.t. number of leaves.


---

### Answer by username_4 on 2020-10-01. Score: 3

I stumbled upon this question now, many years later. In the interim the following paper has appeared:

<https://dl.acm.org/doi/10.1145/3278158>

<https://arxiv.org/abs/1704.08705>

There the authors do precisely what Kaveh asks for in his question 2: they give a (uniform) TC0 algorithm for balancing, hence obtaining an alternative proof of the main result in Buss '87, as was the original motivation of this question.


---

