Circuit Lower Bounds, Help Functions, and the Remote Point Problem

Details Circuit Lower Bounds, Help Functions, and the Remote Point Problem Circuit Lower Bounds, Help Functions, and the Remote Point Problem

2009-11-23

arxiv.org/abs/0911.4337v1

Computer Science

Computational Complexity

Scientific paper

We investigate the power of Algebraic Branching Programs (ABPs) augmented with help polynomials, and constant-depth Boolean circuits augmented with help functions. We relate the problem of proving explicit lower bounds in both these models to the Remote Point Problem (introduced by Alon, Panigrahy, and Yekhanin (RANDOM '09)). More precisely, proving lower bounds for ABPs with help polynomials is related to the Remote Point Problem w.r.t. the rank metric, and for constant-depth circuits with help functions it is related to the Remote Point Problem w.r.t. the Hamming metric. For algebraic branching programs with help polynomials with some degree restrictions we show exponential size lower bounds for explicit polynomials.

Affiliated with

Also associated with

No associations

Rating

Circuit Lower Bounds, Help Functions, and the Remote Point Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Circuit Lower Bounds, Help Functions, and the Remote Point Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Circuit Lower Bounds, Help Functions, and the Remote Point Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-172952