𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Some Lower Bounds for the Complexity of Continuation Methods

✍ Scribed by Jean-Pierre Dedieu; Steve Smale

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
222 KB
Volume
14
Category
Article
ISSN
0885-064X

No coin nor oath required. For personal study only.

✦ Synopsis

In this note we consider the zero-finding problem for a homogeneous polynomial system,

The well-determined (m=n) and underdetermined (m<n) cases are considered together. We also let D=max d i , d=(d 1 , ..., d m ), and

The projective Newton method has been introduced by Shub in [6] and is defined by

article no. CM980486 454 0885-064XΓ‚98 25.00

πŸ“œ SIMILAR VOLUMES

Upper and lower bounds for the average-c
Upper and lower bounds for the average-case complexity of path-search
✍ Pippenger, Nicholas πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 125 KB πŸ‘ 1 views

A channel graph is the union of all paths between a given input and a given output in an interconnection network. At any moment in time, each vertex in such a graph is either idle or busy. The search problem that we consider is to find a path (from the given input to the given output) consisting ent

Lower Bounds for the Complexity of Funct
Lower Bounds for the Complexity of Functions in a Realistic RAM Model
✍ Nader H. Bshouty πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 127 KB

This paper develops a new technique that finds almost tight lower bounds for the complexity of programs that compute or approximate functions in a realistic RAM model. The nonuniform realistic RAM model is a model that uses the arithmetic Γ„ 4 operations q, y, = , the standard bit operation Shift, Ro

Some Bounds for the Number of Blocks
Some Bounds for the Number of Blocks
✍ Ryuzaburou Noda πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 65 KB

Some natural upper bounds for the number of blocks are given. Only a few block sets achieving the bounds except trivial ones are known. Necessary conditions for the existence of such block sets are given.

Some Bounds for the Number of Blocks II
Some Bounds for the Number of Blocks II
✍ Ryuzaburou Noda πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 95 KB

The block sets achieving the bound Ξ²(i) with i = 2 in Proposition 0 is studied. It is proved that such block sets exist if and only if some t-designs with prescribed parameters exist (Theorem 1).

New lower bounds for the size of edge ch
New lower bounds for the size of edge chromatic critical graphs
✍ Yue Zhao πŸ“‚ Article πŸ“… 2004 πŸ› John Wiley and Sons 🌐 English βš– 108 KB πŸ‘ 1 views

## Abstract In this paper, by applying the discharging method, we obtain new lower bounds for the size of edge chromatic critical graphs for small maximum degree Ξ”. Β© 2004 Wiley Periodicals, Inc. J Graph Theory 46: 81–92, 2004