Direction preserving zero point computing and applications (Extended abstract)
We study the connection between the direction preserving zero point and the discrete Brouwer fixed point in terms of their computational complexity. As a result, we derive a PPAD-completeness proof for computing direction preserving zero point, and a matching oracle complexity bound for discrete Bro...
| Main Authors: | , , |
|---|---|
| Format: | Conference item |
| Language: | English |
| Published: |
Springer Berlin Heidelberg
2009
|
| _version_ | 1797110551501864960 |
|---|---|
| author | Deng, X Qi, Q Zhang, J |
| author_facet | Deng, X Qi, Q Zhang, J |
| author_sort | Deng, X |
| collection | OXFORD |
| description | We study the connection between the direction preserving zero point and the discrete Brouwer fixed point in terms of their computational complexity. As a result, we derive a PPAD-completeness proof for computing direction preserving zero point, and a matching oracle complexity bound for discrete Brouwer’s fixed point. Building upon the connection between the two types of combinatorial structures for continuous fixed point theorems, we derive an immediate proof that TUCKER is PPAD-complete for all constant dimensions, extending the results of P´alv¨olgyi for 2D case [20] and Papadimitriou for 3D case [21]. In addition, we obtain a matching algorithmic bound for TUCKER in the oracle model |
| first_indexed | 2024-03-07T07:56:22Z |
| format | Conference item |
| id | oxford-uuid:a10cb495-968d-4b82-97fe-a0f64147f3c7 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T07:56:22Z |
| publishDate | 2009 |
| publisher | Springer Berlin Heidelberg |
| record_format | dspace |
| spelling | oxford-uuid:a10cb495-968d-4b82-97fe-a0f64147f3c72023-08-17T13:26:46ZDirection preserving zero point computing and applications (Extended abstract)Conference itemhttp://purl.org/coar/resource_type/c_5794uuid:a10cb495-968d-4b82-97fe-a0f64147f3c7EnglishSymplectic Elements at OxfordSpringer Berlin Heidelberg2009Deng, XQi, QZhang, JWe study the connection between the direction preserving zero point and the discrete Brouwer fixed point in terms of their computational complexity. As a result, we derive a PPAD-completeness proof for computing direction preserving zero point, and a matching oracle complexity bound for discrete Brouwer’s fixed point. Building upon the connection between the two types of combinatorial structures for continuous fixed point theorems, we derive an immediate proof that TUCKER is PPAD-complete for all constant dimensions, extending the results of P´alv¨olgyi for 2D case [20] and Papadimitriou for 3D case [21]. In addition, we obtain a matching algorithmic bound for TUCKER in the oracle model |
| spellingShingle | Deng, X Qi, Q Zhang, J Direction preserving zero point computing and applications (Extended abstract) |
| title | Direction preserving zero point computing and applications (Extended abstract) |
| title_full | Direction preserving zero point computing and applications (Extended abstract) |
| title_fullStr | Direction preserving zero point computing and applications (Extended abstract) |
| title_full_unstemmed | Direction preserving zero point computing and applications (Extended abstract) |
| title_short | Direction preserving zero point computing and applications (Extended abstract) |
| title_sort | direction preserving zero point computing and applications extended abstract |
| work_keys_str_mv | AT dengx directionpreservingzeropointcomputingandapplicationsextendedabstract AT qiq directionpreservingzeropointcomputingandapplicationsextendedabstract AT zhangj directionpreservingzeropointcomputingandapplicationsextendedabstract |