| Title:
|
Abelova cena pro Aviho Wigdersona (Czech) |
| Title:
|
Abel Prize for Avi Wigderson (English) |
| Author:
|
Pudlák, Pavel |
| Language:
|
Czech |
| Journal:
|
Pokroky matematiky, fyziky a astronomie |
| ISSN:
|
0032-2423 |
| Volume:
|
66 |
| Issue:
|
3 |
| Year:
|
2021 |
| Pages:
|
149-156 |
| Summary lang:
|
Czech |
| . |
| Category:
|
news |
| . |
| Summary:
|
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í. (Czech) |
| MSC:
|
01A70 |
| MSC:
|
68-xx |
| idZBL:
|
Zbl 07675626 |
| . |
| Date available:
|
2021-11-08T15:04:28Z |
| Last updated:
|
2023-09-13 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/149217 |
| . |
| Reference:
|
[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 1948752 |
| Reference:
|
[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. MR 2979856, 10.4007/annals.2012.176.3.3 |
| Reference:
|
[3] Ben-Sasson, E., Wigderson, A.: Short proofs are narrow – resolution made simple.. J. ACM 48 (2001), 149–169. MR 1868713, 10.1145/375827.375835 |
| Reference:
|
[4] Bourgain, J., Katz, N., Tao, T.: A sum-product estimate in finite fields, and applications.. Geom. Funct. Anal. 14 (2004), 27–57. MR 2053599, 10.1007/s00039-004-0451-1 |
| Reference:
|
[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 3678259 |
| Reference:
|
[6] Erdős, P.: Some remarks on the theory of graphs.. Bull. Amer. Math. Soc. 53 (1947), 292–294. 10.1090/S0002-9904-1947-08785-1 |
| Reference:
|
[7] Kabanets, V., Impagliazzo, R.: Derandomizing Polynomial Identity Tests means proving circuit lower bounds.. Comput. Complexity 13 (2004), 1–46. MR 2105971, 10.1007/s00037-004-0182-6 |
| Reference:
|
[8] Karchmer, M., Wigderson, A.: Monotone circuits for connectivity require super-logarithmic depth.. SIAM J. Discrete Math. 3 (1990), 255–265. 10.1137/0403021 |
| Reference:
|
[9] Nisan, N., Wigderson, A.: Hardness vs randomness.. J. Comput. System Sci. 49 (1994), 149–167. 10.1016/S0022-0000(05)80043-1 |
| Reference:
|
[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 2131412 |
| Reference:
|
[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. MR 1888797, 10.2307/3062153 |
| Reference:
|
[12] Wigderson, A.: Mathematics and computation: A theory revolutionizing technology and science.. Princeton University Press, 2019. MR 4205964 |
| . |
