Theory of Machines and Languages 40415 
  CE Department- Sharif University of Technology Fall 83 - Group 1 

  Main Menu
   Discussion Area


  1383-11-26 February 14, 2005 01:07 PM  
The last version of Grades annonced.


  1383-11-10 January 29, 2005 05:34 PM  
Dear All,
The Seminars will be at next Sunday 8:00 AM
Siavosh Benabbas

  1383-11-07 January 26, 2005 02:16 PM  
Dear All,
You will have 25-40 minutes to present depending on your choice, but
you will have to present at least the headings I have placed in the
topic. If it is a theorem you have to give at least the idea of the
proof, unless it is an "Introduction" Seminar. Please don't hesitate
to ask if something specific should be presented or not.
Siavosh Benabbas

  1383-11-07 January 26, 2005 02:20 PM  
Dear All,
These are the topics of presentation. They are relativly hard, and
need efort to understand, let alone present. If you choose one of
these you SHOULD work in a team of two, doing them alone would be
really hard anyway. You should send me your groups/topics by Thursday,
the presentations will, most probably, be on the next Sunday(1/30/2005
I guess). I have listed a refrance for each of the topics. Using
Powerpoints, OpenOffice presentation or properly sized PDFs is
mandatory to your presentation. You should also hand in a 2 to 3 page
report along with a PDF or powerpoint version of the presentation,
though I think that can wait till some time in the next week.
You can come up with your own topics if you want, or choose one of
these, but these peaple are exceptions as they have already sent me
their titles:
Zeinab Abbasi -----------> on the current state of the P versus NP question.
Makan Sepehrifar -------> NL=co-NL (Use arora Book part 3.3, or
Sipser's Book 8.6)
Kian Mirjalali --------------> IP=PSPACE
They too can choose teammates, or change their topics till Tuesday but
can NOT choose one of the other topics I have sent.

I have given one or two possible sources for you.
I have used Sipser's Book as a shorcut for Prof. Sipser's marvelous
Book "Introduction to the Theory of Computation"
I have used Arora's Book and Arora's Book 2 as a shortcut for Dr.
Arora's Lecture notes volume one and two they can be downloaded from
and the list is:

I advise against selecting the Zero-Knowledge topic if you don't know
anything about the topics, I also consider the last subject (PCP)
The subjects are marked by a - dash ;-)
please note that as the topics are limited priority is with those that
will email me first, and that if you don't choose the subject till
Tuesday I supose that you don't want to present (No marks are ofcourse
subtracted if you cancel your presentation know.)
Best Regards & Good Lock,
Siavosh Benabbas
sbenabas at gmail dot com

Advanced Topics in the Theory of Computation:
- The Recursion Theorem                                                                       (Sipser 6.1)
- Decidability/Undecidability of Logic Theories                                               (Sipser 6.2)
- A Definition of Information                                                                 (Sipser 6.4)

Other models of computation that are closly related to Turing Machines:
- Introduction to \lambda-calculus                                                            
- Introduction to the Polynomial Hierarchy                                                    (Use Arora Book C5)
- Randomization(BBP, RP, ZPP) basics, biased coins, k-sided coins, RP \in BPP, BPP \in Polynomial Sizer Circuits (Use Arora Book2 C7)
- Interactive Proofs, Arthur-Merlin Game, and introduction to Zero-Knowledge                  (Sipser 10.4 except for IP=PSPACE and O. Goldreich,  Randomness, Interaction, Proofs and Zero-Knowledge (a survey) )

space complexity:
- Definition of Space complexity,savith's Theorem, and NSPACE(f(n)) \in NSPACE(f(n)^2)        (Use Arora Book C3.3, or Sipser 8.1)
- PSPACE, PSPACE-completeness, and PSPACE-completeness of TQBF                                (Use Arora Book C3.1, or Sipser 8.3)

Advanced/Recent Complexity:
- Introduction to the PCP theorem and its use in unapproximability                            (See Dr. Arora's thesis for example.)

  1383-11-05 January 24, 2005 12:02 PM  
Dear Students
The grades of Final Exam and the Adjusted Grades have been announced.
Please note:
1- I will send your grades as Round(Adjusted+1).
2- Adjusted= Mid1*1.2 + Mid2*1.2 + Final*1.1 + Exc.
3- Please send your objections about each exams grades to until 1383/11/8.
If your objection be incorrect, I will ignore its adjustment and one point extra grade.


  1383-10-29 January 18, 2005 11:45 AM  
Dear Students
If you have any objection about your grades please wait. I will define a procedure for the process of your grades review. This will be after the annoncement of final and excercises grades.


  1383-10-27 January 16, 2005 07:51 PM  
The Grades of First and Second MidTerm Exams  Have been Annonced. See Grades Bar.(First exam from 5.5 and the second from 4)

  1383-10-21 January 10, 2005 01:48 PM  
The Grades of Second MidTerm Exam (From 4) Have been Annonced. See Grades Bar.

  1383-10-15 January 04, 2005 02:50 PM  
Hi all
The last exercise class will be held tomarro in the previous class @  12-13.30

  1383-09-22 December 12, 2004 12:30 PM  

The subject of my lectures in the main class from 24 Azar until the end of this term will be:

Spacial Topics in Automata on Infinite Objects ( Infinite Strings and Trees)

Thus all registered student of this course must attend these sessions.


  1383-09-03 November 23, 2004 12:36 PM  
Hi All ,Here is date of the 1st , the 2nd midter and the final exam:

1st mid:1383/9/8 TALAR-e-3 ;Time:12:30-15

2nd mid:1383/9/29 TALAR-e-3 ;Time:12:30-15

Final Exam 1383/10/19

  1383-08-04 October 25, 2004 09:57 AM  
Dear all!
The first , the second and the third series of the exercises has been copied, so you can get them from publish room.
The deadline : (Sunday) 10th the Aban

  1383-07-12 October 03, 2004 02:33 PM  
Dear students :
Here is the course homepage, so every thing about this course annouce here.

 This website is visited 3352 times since October 2004. Updated Monday 2015-04-06 12:22