Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Quadratic maps are hard to sample
Viola E. ACM Transactions on Computation Theory8 (4):1-4,2016.Type:Article
Date Reviewed: Jul 26 2016

A quadratic map is a function of the form f (x) = ax2 + bx + c, or more generally,

.

The only simpler polynomials are those of degree 1, omitting the terms aijxixj, and the constants f(x) = c. This delightful short note proves that quadratic maps, simple as they may seem, are hard to sample. That means there is no constant-depth circuit of size polynomial in n and complexity AC0 that outputs the probability distribution (x,f (x)), where x is uniformly distributed. This is in contrast to degree 1 maps, which can be sampled by an AC0 circuit by a theorem of Babai. A quadratic map that cannot be sampled is explicitly constructed, where x ranges over the field 0,1 with two elements. Namely, the counterexample is the composition of the inner product quadratic map (x1, … xn) ↦ x1x2 + x2x3 + … + xn - 1 xn with a random linear transformation. This is remarkable because the inner product quadratic map on its own can be sampled with an AC0 circuit. This example advances the understanding of which maps can be samples in AC0.

Reviewer:  Chris Heunen Review #: CR144633 (1611-0827)
Bookmark and Share
 
Numerical Algorithms And Problems (F.2.1 )
 
 
Statistical Computing (G.3 ... )
 
 
Complexity Measures And Classes (F.1.3 )
 
Would you recommend this review?
yes
no
Other reviews under "Numerical Algorithms And Problems": Date
On the computational complexity of ordinary differential equations
Ko K. (ed) Information and Control 58(1-3): 157-194, 1984. Type: Article
Jun 1 1985
The computational complexity of simultaneous diophantine approximation problems
Lagarias J. SIAM Journal on Computing 14(1): 196-209, 1985. Type: Article
Jan 1 1986
Parallel and distributed computation: numerical methods
Bertsekas D., Tsitsiklis J., Prentice-Hall, Inc., Upper Saddle River, NJ, 1989. Type: Book (9789780136487005)
Apr 1 1990
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy