Geodesic
Abelova cena pro Aviho Wigdersona
Pokroky matematiky, fyziky a astronomie, Tome 66 (2021) no. 3, pp. 149-156
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

Abelovu cenu za rok 2021 získali společně László Lovász a Avi Wigderson za zásadní přínos v teoretické informatice a diskrétní matematice. V tomto článku představíme čtenářům Aviho Wigdersona a jeho práci výběrem tří důležitých výsledků z jeho mnoha publikací.
Abelovu cenu za rok 2021 získali společně László Lovász a Avi Wigderson za zásadní přínos v teoretické informatice a diskrétní matematice. V tomto článku představíme čtenářům Aviho Wigdersona a jeho práci výběrem tří důležitých výsledků z jeho mnoha publikací.
Classification : 01A70, 68-xx 
@article{PMFA_2021_66_3_a0,
     author = {Pudl\'ak, Pavel},
     title = {Abelova cena pro {Aviho} {Wigdersona}},
     journal = {Pokroky matematiky, fyziky a astronomie},
     pages = {149--156},
     year = {2021},
     volume = {66},
     number = {3},
     zbl = {07675626},
     language = {cs},
     url = {http://geodesic.mathdoc.fr/item/PMFA_2021_66_3_a0/}
}
TY  - JOUR
AU  - Pudlák, Pavel
TI  - Abelova cena pro Aviho Wigdersona
JO  - Pokroky matematiky, fyziky a astronomie
PY  - 2021
SP  - 149
EP  - 156
VL  - 66
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/PMFA_2021_66_3_a0/
LA  - cs
ID  - PMFA_2021_66_3_a0
ER  - 
%0 Journal Article
%A Pudlák, Pavel
%T Abelova cena pro Aviho Wigdersona
%J Pokroky matematiky, fyziky a astronomie
%D 2021
%P 149-156
%V 66
%N 3
%U http://geodesic.mathdoc.fr/item/PMFA_2021_66_3_a0/
%G cs
%F PMFA_2021_66_3_a0
Pudlák, Pavel. Abelova cena pro Aviho Wigdersona. Pokroky matematiky, fyziky a astronomie, Tome 66 (2021) no. 3, pp. 149-156. http://geodesic.mathdoc.fr/item/PMFA_2021_66_3_a0/

[1] Alon, N., Lubotzky, A., Wigderson, A.: Semi-direct product in groups and zig-zag product in graphs: Connections and applications. 42nd IEEE Symposium on Foundations of Computer Science, Las Vegas, NV, 2001, IEEE Computer Soc., Los Alamitos, CA, 2001, 630–637. | MR

[2] Barak, B., Rao, A., Shaltiel, R., Wigderson, A.: 2-source dispersers for $n^{o(1)}$ entropy, and Ramsey graphs beating the Frankl-Wilson construction. Ann. of Math. 176 (2012), 1483–1544. | DOI | MR

[3] Ben-Sasson, E., Wigderson, A.: Short proofs are narrow – resolution made simple. J. ACM 48 (2001), 149–169. | DOI | MR

[4] Bourgain, J., Katz, N., Tao, T.: A sum-product estimate in finite fields, and applications. Geom. Funct. Anal. 14 (2004), 27–57. | DOI | MR

[5] Cohen, G.: Towards optimal two-source extractors and Ramsey graphs. STOC’17 – Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, 2017, 1157–1170. | MR

[6] Erdős, P.: Some remarks on the theory of graphs. Bull. Amer. Math. Soc. 53 (1947), 292–294. | DOI

[7] Kabanets, V., Impagliazzo, R.: Derandomizing Polynomial Identity Tests means proving circuit lower bounds. Comput. Complexity 13 (2004), 1–46. | DOI | MR

[8] Karchmer, M., Wigderson, A.: Monotone circuits for connectivity require super-logarithmic depth. SIAM J. Discrete Math. 3 (1990), 255–265. | DOI

[9] Nisan, N., Wigderson, A.: Hardness vs randomness. J. Comput. System Sci. 49 (1994), 149–167. | DOI

[10] Pudlák, P., Rödl, V.: Pseudorandom sets and explicit constructions of Ramsey graphs. In: Krajíček, J. (ed.): Complexity of Computations and Proofs, Quaderni di Matematica, vol. 13, Caserta, 2004, 327–346. | MR

[11] Reingold, O., Vadhan, S., Wigderson, A.: Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors. Ann. of Math. 155 (2002), 157–187. | DOI | MR

[12] Wigderson, A.: Mathematics and computation: A theory revolutionizing technology and science. Princeton University Press, 2019. | MR