Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > HELP FUNCTIONS:
Reports tagged with Help functions:
TR09-122 | 23rd November 2009
Vikraman Arvind, Srikanth Srinivasan

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

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 ... more >>>




ISSN 1433-8092 | Imprint