Mi pregunta se refiere a la prueba del principal teorema de Ajtai en su innovador artículo de 1996, Generando instancias difíciles de problemas de red , lo que indica una conexión entre los problemas de red dura de peor caso y de media. Esta prueba me es difícil de entender. ¿Existe una exposición clara de esta prueba en la literatura?
integer-lattice
Krishnan Narayanan
fuente
fuente
Respuestas:
Puede intentar leer documentos más recientes, como Reducciones del peor caso al promedio, basados en medidas gaussianas de Miccancio y Regev, o las notas de la conferencia de Regev sobre el tema (es posible que desee leer todo el curso ).
fuente