Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAND and/or OR: Uniform Polynomial-Size Circuits
103
0
0.0
(
0
)
Added by
EPTCS
Publication date
2012
fields
Informatics Engineering
and research's language is
English
Authors
Niall Murphy
Ask ChatGPT about the research
No Arabic abstract
We investigate the complexity of uniform OR circuits and AND circuits of polynomial-size and depth. As their name suggests, OR circuits have OR gates as their computation gates, as well as the usual input, output and constant (0/1) gates. As is the norm for Boolean circuits, our circuits have multiple sink gates, which implies that an OR circuit computes an OR function on some subset of its input variables. Determining that subset amounts to solving a number of reachability questions on a polynomial-size directed graph (which input gates are connected to the output gate?), taken from a very sparse set of graphs. However, it is not obvious whether or not this (restricted) reachability problem can be solved, by say, uniform AC^0 circuits (constant depth, polynomial-size, AND, OR, NOT gates). This is one reason why characterizing the power of these simple-looking circuits in terms of uniform classes turns out to be intriguing. Another is that the model itself seems particularly natural and worthy of study. Our goal is the systematic characterization of uniform polynomial-size OR circuits, and AND circuits, in terms of known uniform machine-based complexity classes. In particular, we consider the languages reducible to such uniform families of OR circuits, and AND circuits, under a variety of reduction types. We give upper and lower bounds on the computational power of these language classes. We find that these complexity classes are closely related to tallyNL, the set of unary languages within NL, and to sets reducible to tallyNL. Specifically, for a variety of types of reductions (many-one, conjunctive truth table, disjunctive truth table, truth table, Turing) we give characterizations of languages reducible to OR circuit classes in terms of languages reducible to tallyNL classes. Then, some of these OR classes are shown to coincide, and some are proven to be distinct. We give analogous results for AND circuits. Finally, for many of our OR circuit classes, and analogous AND circuit classes, we prove whether or not the two classes coincide, although we leave one such inclusion open.
rate research
Read More
We reprove that the approximate degree of the OR function on n bits is Omega(sqrt(n)). We consider a linear program which is feasible if and only if there is an approximate polynomial for a given function, and apply the duality theory. The duality theory says that the primal program has no solution if and only if its dual has a solution. Therefore one can prove the nonexistence of an approximate polynomial by exhibiting a dual solution, coined the dual polynomial. We construct such a polynomial.
We prove a simple, nearly tight lower bound on the approximate degree of the two-level $mathsf{AND}$-$mathsf{OR}$ tree using symmetrization arguments. Specifically, we show that $widetilde{mathrm{deg}}(mathsf{AND}_m circ mathsf{OR}_n) = widetilde{Omega}(sqrt{mn})$. We prove this lower bound via reduction to the $mathsf{OR}$ function through a series of symmetrization steps, in contrast to most other proofs that involve formulating approximate degree as a linear program [BT13, She13, BDBGK18]. Our proof also demonstrates the power of a symmetrization technique involving Laurent polynomials (polynomials with negative exponents) that was previously introduced by Aaronson, Kothari, Kretschmer, and Thaler [AKKT19].
We show a nearly quadratic separation between deterministic communication complexity and the logarithm of the partition number, which is essentially optimal. This improves upon a recent power 1.5 separation of Goos, Pitassi, and Watson (FOCS 2015). In query complexity, we establish a nearly quadratic separation between deterministic (and even randomized) query complexity and subcube partition complexity, which is also essentially optimal. We also establish a nearly power 1.5 separation between quantum query complexity and subcube partition complexity, the first superlinear separation between the two measures. Lastly, we show a quadratic separation between quantum query complexity and one-sided subcube partition complexity. Our query complexity separations use the recent cheat sheet framework of Aaronson, Ben-David, and the author. Our query functions are built up in stages by alternating function composition with the cheat sheet construction. The communication complexity separation follows from lifting the query separation to communication complexity.
Let $C$ be a depth-3 arithmetic circuit of size at most $s$, computing a polynomial $ f in mathbb{F}[x_1,ldots, x_n] $ (where $mathbb{F}$ = $mathbb{Q}$ or $mathbb{C}$) and the fan-in of the product gates of $C$ is bounded by $d$. We give a deterministic polynomial identity testing algorithm to check whether $fequiv 0$ or not in time $ 2^d text{ poly}(n,s) $.
The structure of Gamma-Ray Burst (GRB) jets impacts on their prompt and afterglow emission properties. Insights into the still unknown structure of GRBs can be achieved by studying how different structures impact on the luminosity function (LF): i) we show that low ($10^{46} < L_{rm iso} < 10^{48}$ erg/s) and high (i.e. with $L_{rm iso} > 10^{50}$ erg/s) luminosity GRBs can be described by a unique LF; ii) we find that a uniform jet (seen on- and off-axis) as well as a very steep structured jet (i.e. $epsilon(theta) propto theta^{-s}$ with $s > 4$) can reproduce the current LF data; iii) taking into account the emission from the whole jet (i.e. including contributions from mildly relativistic, off-axis jet elements) we find that $E_{rm iso}(theta_{rm v})$ (we dub this quantity apparent structure) can be very different from the intrinsic structure $epsilon(theta)$: in particular, a jet with a Gaussian intrinsic structure has an apparent structure which is more similar to a power law. This opens a new viewpoint on the quasi-universal structured jet hypothesis.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
