Theoretical Aspects of Computer Science : Advanced Lectures (Lecture Notes in Computer Science Vol.2292) (2002. 220 p. w. figs. 23,5 cm)

TheFirstSummerSchoolonTheoreticalAspectsonComputerSciencewasheld attheInstituteforStudiesinTheoreticalPhysicsandMathematics(IPM)from July3-10,2000. Theideaoforganizingasummerschoolwasoriginatedduringaconversation betweenthe?rstandthesecondeditorofthisvolumeinthewinterof2000at IPMinTehran. ThedecisionwasformalizedwhenthethirdeditorvisitedIPM laterinthewinter. ThemainideabehindtheSummerSchoolwastointroducetothestudents in Iran some of the highly innovative and promising research in Theoretical ComputerScience,and,atthesametime,tostarta?owofideasbetweentop researchersinthe?eldandtheIranianscientists. Forthisreason,thetalkswere designedtobeofatutorialstyle. Theorganizersdecidedtoconcentrateonafewimportantareasofresearch in modern Theoretical Computer Science. To attract students to this imp- tant area, they also decided to include talks on applications of methods from TheoreticalComputerSciencetootherareas. ThisvolumecontainsthewrittencontributionstotheprogramofthisS- mer School. It is intended for students and researchers who want to gain - quaintancewithcertaintopicsinTheoreticalComputerScience. Thepaperson quantumcomputation,approximationalgorithms,self-testing/correcting,al- braic modeling of data, and the Regularity Lemma correspond to the former category,whileconnectionsbetweenmultipleaccesscommunicationandcom- natorialdesigns,graph-theoreticalmethodsincomputervision,andlow-density parity-checkcodesbelongtothelattercategory. Eachcontributiontothisvolumewaspresentedinatwohoursession,l- vingampletimeforquestionsanddiscussions. Thetutorialswerefollowedbya numberofspecializedtalkstouchingoncurrentresearchproblemsinthearea. Partsofthetalkshavebeenincorporatedintothematerialofthecontributions. January2002 G. B. Khosrovshahi A. Shokoufandeh A. Shokrollahi Organization The ?rst International Summer School on Theoretical Aspects of Computer Science was organized by the Institute for Studies in Theoretical Physics and Mathematics(IPM)inTehran,Iran. ProgramCommittee Conferen