Content deleted Content added
Citation bot (talk | contribs) Alter: template type, journal. Add: doi-access, pmid, doi, s2cid, isbn, volume, year, series, title, authors 1-1. Removed parameters. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Chris Capoccia | #UCB_toolbar |
Erel Segal (talk | contribs) |
||
Line 80:
== Communication complexity ==
Roughgarden and Weinstein<ref>{{Cite journal |last1=Roughgarden |first1=Tim |last2=Weinstein |first2=Omri |date=2016-10-01 |title=On the Communication Complexity of Approximate Fixed Points |url=https://ieeexplore.ieee.org/document/7782935 |journal=2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS) |pages=229–238 |doi=10.1109/FOCS.2016.32|isbn=978-1-5090-3933-3 |s2cid=87553 }}</ref> studied the [[communication complexity]] of computing an approximate fixed-point. In their model, there are two agents: one of them knows a function ''f'' and the other knows a function ''g''. Both functions are Lipschitz continuous and satisfy Brouwer's conditions. The goal is to compute an approximate fixed point of the [[composite function]] <math>g\circ f</math>. They show that the deterministic communication complexity is in <math>\Omega(2^d)</math>.
== Further reading ==
* Equilibria, fixed points, and complexity classes: a survey.<ref>{{Cite journal |last=Yannakakis |first=Mihalis |date=2009-05-01 |title=Equilibria, fixed points, and complexity classes |url=https://www.sciencedirect.com/science/article/pii/S1574013709000161 |journal=Computer Science Review |language=en |volume=3 |issue=2 |pages=71–85 |doi=10.1016/j.cosrev.2009.03.004 |issn=1574-0137}}</ref>
== References ==
| |||