Reduced error pruning of branching programs cannot be approximated to within a logarithmic factor

DOI10.1016/S0020-0190(03)00255-2zbMATH Open1175.68562MaRDI QIDQ1014397FDOQ1014397

Authors: Richard Nock, Tapio Elomaa, Matti Kääriäinen 

Publication date: 28 April 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Recommendations

• The difficulty of reduced error pruning of leveled branching programs
• scientific article; zbMATH DE number 3913677
• scientific article; zbMATH DE number 706832
• Error reduction for weighted PRGs against read once branching programs
• scientific article; zbMATH DE number 7561753
• Stochastic Algorithms: Foundations and Applications
• scientific article; zbMATH DE number 18624
• A lower bound for read-once-only branching programs
• Branching program size is almost linear in formula size
• Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication

zbMATH Keywords

algorithmsinapproximabilitybranching programreduced error pruning

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Cites Work

• Title not available (Why is that?)
• A threshold of ln n for approximating set cover
• Title not available (Why is that?)
• Some optimal inapproximability results
• The difficulty of reduced error pruning of leveled branching programs
• Boosting using branching programs
• Title not available (Why is that?)

Cited In (1)

• The difficulty of reduced error pruning of leveled branching programs

Uses Software

• C4.5

This page was built for publication: Reduced error pruning of branching programs cannot be approximated to within a logarithmic factor

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1014397)