Timeline for What is the comparator circuit?
Current License: CC BY-SA 4.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 9, 2021 at 15:18 | vote | accept | Turbo | ||
| Jun 9, 2021 at 12:46 | comment | added | Yuval Filmus | CC circuits have no fan-out. | |
| Jun 9, 2021 at 12:39 | comment | added | Turbo | Consider a layered $SAC^i$ where unbounded fanin $OR$ alternates bounded fanin $AND$. $OR$ can be replaced by $CC^1$ circuits while $AND$ by $CC^0$. It appears $SAC^i$ should be in $CC^{i+1}$ but maybe there is a reason the substitution cannot be performed. | |
| Jun 9, 2021 at 12:01 | comment | added | Turbo | Ok I am surprised NC is not in CC if we are considering comparator circuits to be of arbitrary depth while NC by definition is of polylog depth. | |
| Jun 9, 2021 at 11:56 | comment | added | Yuval Filmus | Perhaps the authors simply didn’t care about the depth in the case of comparator circuits. | |
| Jun 9, 2021 at 10:18 | comment | added | Turbo | "..$\Omega(n)$ depth". | |
| Jun 9, 2021 at 10:10 | comment | added | Turbo | Honestly on page $33$ it talks of a machine model corresponding to a characterization in theorem $12$. But it appears at best murky and totally unclear what the depth should be? At every place $CC$ is utilized the terminology $CC^i$ is avoided and I am not sure if it is intentional because of uncertainty in depth or it is avoided for a reason and figure $14$ clearly indicates $\omega(n)$ depth (since it illustrates an example of reachability on $5$ vertices by repeating a gadget $5$ times). | |
| Jun 9, 2021 at 10:04 | comment | added | Yuval Filmus | All current knowledge is summarized in the paper. If it’s not there, it’s not known. | |
| Jun 9, 2021 at 9:55 | comment | added | Turbo | I see $NC^2$ is in quasi-poly $NC^2$-formula but not known to be in $NC^2$ formula. Makes sense. So is $NL$ in $CC^1$ (I really am unable to infer in the paper)? On basis of the comment it appears since perfect matching is not in $NL$. It appears perfect matching might be in $CC^2$ but uncertain. | |
| Jun 9, 2021 at 9:54 | comment | added | Yuval Filmus | If the fan-out is 1 then you have a formula. They can be simulated in CC. It is conjectured that formulas are less powerful than circuits (in terms of complexity). | |
| Jun 9, 2021 at 9:50 | comment | added | Turbo | Say you have a formula of $AND$ and $OR$ having negated inputs and no $NOT$ gates. Say fan-out is $1$ and fan-in is $2$. For every $AND$ gate can't we introduce a dummy $OR$ gate and for every $OR$ gate can't we introduce dummy $AND$ gate? Technically the wires which are not being used again can be used to route dummy information (the desired output position changes) but it appears we can embed $NC$ formula in $CC$ circuits of similar depth and for every $NC$-formula we compute the correct output wire and utilizing polynomially many additional wires route the correct output wire to the top. | |
| Jun 9, 2021 at 9:46 | comment | added | Yuval Filmus | You can implement CC using a usual circuit, but not the other way around. | |
| Jun 9, 2021 at 9:44 | comment | added | Turbo | It appears $CC$ seems to be having identical straightline representation to any boolean circuit where number of instructions which do not erase the inputs is $0$. We can introduce dummy instructions $z\leftarrow z$ or $z\leftarrow{garbage}$ if we are not using the input variables $z$ again in the straightline representation of the boolean formula. | |
| Jun 9, 2021 at 9:37 | comment | added | Yuval Filmus | The difference is that in usual circuits, we allow instructions which don’t erase the inputs. | |
| Jun 9, 2021 at 9:32 | comment | added | Turbo | The straightline representation is interesting but so can any Boolean formula be given as a straightline having negated inputs and OR and AND gates and we can reuse variables and if we desire to keep number of variables in every layer similar we can update the unused variables in a dummy manner. | |
| Jun 9, 2021 at 8:26 | history | answered | Yuval Filmus | CC BY-SA 4.0 |