Article
Full entry |
PDF
(0.6 MB)
Feedback
PDF
(0.6 MB)
Feedback
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í.
References:
[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
[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 10.4007/annals.2012.176.3.3 | MR 2979856
[3] Ben-Sasson, E., Wigderson, A.: Short proofs are narrow – resolution made simple. J. ACM 48 (2001), 149–169. DOI 10.1145/375827.375835 | MR 1868713
[4] Bourgain, J., Katz, N., Tao, T.: A sum-product estimate in finite fields, and applications. Geom. Funct. Anal. 14 (2004), 27–57. DOI 10.1007/s00039-004-0451-1 | MR 2053599
[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
[6] Erdős, P.: Some remarks on the theory of graphs. Bull. Amer. Math. Soc. 53 (1947), 292–294. DOI 10.1090/S0002-9904-1947-08785-1
[7] Kabanets, V., Impagliazzo, R.: Derandomizing Polynomial Identity Tests means proving circuit lower bounds. Comput. Complexity 13 (2004), 1–46. DOI 10.1007/s00037-004-0182-6 | MR 2105971
[8] Karchmer, M., Wigderson, A.: Monotone circuits for connectivity require super-logarithmic depth. SIAM J. Discrete Math. 3 (1990), 255–265. DOI 10.1137/0403021
[9] Nisan, N., Wigderson, A.: Hardness vs randomness. J. Comput. System Sci. 49 (1994), 149–167. DOI 10.1016/S0022-0000(05)80043-1
[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
[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 10.2307/3062153 | MR 1888797
[12] Wigderson, A.: Mathematics and computation: A theory revolutionizing technology and science. Princeton University Press, 2019. MR 4205964
Search
Partner of
