nishi@utai.UUCP (09/08/87)
The time has come to decide on a weekly meeting time for this year's student seminar. Stephen, who scheduled speakers last year, would like to spend more time on his Master's (not unreasonable considering the January 30 deadline). I am willing to do the scheduling, but I have the same deadline. Anyone who is past the deadline and willing to do the job is more than welcome to do so. Rather than trying to find a time to call a meeting to discuss when to have meetings, I will instead ask each of you to give me a list of times during the week when you have other things scheduled (and hence will be unable to attend a seminar meeting), and also a list of your first, second, and third choices of times to meet. If you don't enform me of your conflicts, I'll assume that you are not interested in attending our meetings or that all times are equally suitable for you. I'll choose the meeting time that adversely affects the smallest number of people. Please don't wait until after I've chosen a time to tell me that you can't make it; by then it will be too late. Send me your preferences by Friday, September 11; check postings on Tuesday, September 14 for the meeting time that week. We might use the first meeting as an opportunity to introduce ourselves to and get to know the new theory students. Hoping to hear from you soon, Naomi Nishimura
nishi@utai.UUCP (09/21/87)
Our meeting time this term will be either 2-3 or 3-4 on Wednesdays, depending on when I can schedule a room. My apologies to those of you who will be unable to attend at that time -- there is no time during the week which doesn't present a problem to at least two people. As soon as I know the room and the time, I will post both, even if it's as late as Wednesday morning. We will meet this week for new and old students to get to know each other. Prabhakar and I will supply refreshments. Please let me know if you wish to volunteer either to talk or to bring food for future meetings. Thanks. --Naomi
nishi@utai.UUCP (09/28/87)
This week's speaker will be Stephen Bellantoni, who will introduce Kolmogorov complexity, including both basic definitions and an application to PRAM lower bounds. The meeting will be held in GB412 from 2:00-3:00 on Wednesday, September 30. Please remember that no background in the area is assumed; feel free to come and ask lots of questions.
nishi@utai.UUCP (10/12/87)
Due to FOCS, there will be no meeting of the student seminar this week. Next week there will definitely be a meeting, and there will possibly be food, the latter only if someone volunteers. I have three more speakers lined up, and after that I'll have to start twisting arms. Arm-twisting will begin even sooner for food. Volunteer now and avoid being nagged later . . .
nishi@utai.UUCP (10/19/87)
This week I will introduce relativized complexity. The meeting will be held in GB412 from 2:00-3:00 on Wednesday, October 21. Problems in relatived complexity deal with the relations between standard complexity classes given the additional power of an oracle; the oracle may be either constructed specifically for a particular problem or chosen at random. The talk will include basic definitions and results using both kinds of oracles. Please remember that no background in the area is assumed; feel free to come and ask lots of questions. We still need a volunteer for refreshments this week; please contact me immediately if you are willing to help out.
nishi@utai.UUCP (10/26/87)
This week's speaker will be Wayne Eberly, who will be talking on decompositions of algebras. The meeting will be held in GB412 from 2:00-3:00 on Wednesday, October 28. In the talk recent results about decompositions of finite dimensional algebras will be discussed. Relations to other (interesting) computational problems, such as factorization of polynomials, will be emphasized. Wayne promises to try hard not to bury us all in algebra. Please remember that no background in the area is assumed; feel free to come and ask lots of questions.
nishi@utai.UUCP (11/02/87)
This week's speaker will be Mark Giesbrecht, who will discuss decomposition of polynomials, I think. The meeting will be held in GB412 from 2:00-3:00 on Wednesday, November 4. There are still slots open for several speakers and several food providers: contact me for exact dates. Please remember that no background in the area is assumed; feel free to come and ask lots of questions.
nishi@utai.UUCP (11/02/87)
Here's a brief descripton of the talk Mark will be giving on Wednesday: The decomposition of polynomials has received considerable attention recently in computer science. Given a polynomial f, we wish to find polynomials g and h of specified degrees such that f=g(h). The complexity of the problem varies wildly depending on the ground field and the degree of the polynomial involved. We will look at some of the the computational problems as well as some generalisations (such as multivariate polynomials and rational functions). Once again an attempt will be made not to hide behind a wall of algebra.
nishi@utai.UUCP (11/09/87)
This week's speaker will be Bruce Kapron, who will speak about definability and complexity. The meeting will be held in GB412 from 2:00-3:00 on Wednesday, November 11. We will discuss the characterization of some complexity classes via definability over finite structures in extended first order languages. Some knowledge of first order logic is assumed.
nishi@utai.UUCP (12/07/87)
Due to lack of speakers, there will be no more seminar meetings this term. Unless someone kindly offers to relieve me of the post, I will be organizing meeting times for next term. As before, I will choose the meeting time which allows the largest number of people to attend. To let me know your conflicts and preferences, you can either pick up a form from me (4301A), or make up your own. I will want these back by the end of the first week of classes so that there is enough time to book a room. If you can be coerced to speak (or provide food) at all next term, please let me know as soon as possible: due to my January thesis deadline, I will be unable to spend much time threatening you next month.
nishi@utai.UUCP (Naomi Nishimura) (01/03/88)
The time for scheduling has come again. Please let me know your schedule by Friday, January 8 so that I can determine a suitable meeting time and book a room for us. I have forms in my office: fill out one of mine, or make up your own. I will also need volunteers for making food and giving talks.
nishi@utai.UUCP (Naomi Nishimura) (01/08/88)
This is a final call for lists of conflicts and preferences for meeting times. If I have not received either a schedule (or a plea for more time to submit a schedule) from you by this weekend, I will assume that you have no preference, and no conflicts other than theory classes, the Tuesday colloqium, and the Thursday theory seminar. Scheduling forms can be picked up from me in 4301a, or you can make up your own. Please deliver schedules to 4301a, my mailbox, or nishi@yonge.csri. Thank you.
nishi@utai.UUCP (Naomi Nishimura) (01/12/88)
The tentative meeting time for the seminar will be Thursdays at 11:00; I will post a confirmation as soon as I am notified that we have a room booked. My apologies to those of you who don't wish to come in on Thursdays or before noon; my alternative would have been to schedule a meeting at a time when at least one person had a conflict. The first meeting will be announced as soon as I get a least one volunteer to speak. Please let me know if you are the one, or if you will be willing to speak later in the term.
nishi@utai.UUCP (Naomi Nishimura) (01/16/88)
We have a room for seminar meetings: Wallberg 144 from 11 to 12 on Thursdays. What we don't have is speakers. Volunteers?
nishi@utai.UUCP (Naomi Nishimura) (02/02/88)
There WILL be a meeting this week, at 11:00 in Wallberg 144. Hazel will be speaking on a topic yet to be announced. As yet, no one has volunteered to bring food for this or any other talk. Please let me know whether you are willing to either talk or provide food. Thanks.
nishi@utai.UUCP (Naomi Nishimura) (02/02/88)
This week's speaker will be Hazel Everett. The meeting will be held in Wallberg 144 from 11:00-12:00 on Thursday, February 4. Hazel will be speaking about "Shape from Probing". This talk will describe the contents of a paper by Cole and Yap which describes a new problem in robotics: how to determine the shape and position of an object using probes. For convex polygons they show an elegant method for solving this problem using 3n probes and prove this is optimal. Volunteers for providing food are still sought, for both this and subsequent meetings.
nishi@ai.toronto.edu (Naomi Nishimura) (02/09/88)
This week's speaker will be Murray Sherk, who will give a talk entitled "How Splay Trees Are Efficient." The meeting will be held in Wallberg 144 from 11:00-12:00 on Thursday, February 11. Murray will be using amortized complexity measures to show the efficiency of splay trees. If you attended his talk on the subject, you'll be in great shape; if not, don't worry, you should still be able to understand.
nishi@ai.toronto.edu (Naomi Nishimura) (02/11/88)
There will be no student seminar during reading week (unless someone else would like to organize one); the next seminar will be given by Steve Bellantoni, on February 25. Can anyone be convinced to provide food that day, or to provide food or speak at a later date? Please let me know.
nishi@ai.toronto.edu (Naomi Nishimura) (02/22/88)
This week's speaker will be Stephen Bellantoni. He will present ideas from "Diversity-Based Inference of Finite Automata", a paper by Rivest and Schapire in 28th FOCS. This paper introduces the "diversity" measure of automata complexity and gives a randomized algorithm for learning the structure of a finite automata in time polynomial in the diversity + 1/(probability of error). He plans to start promptly at 10 past 11, Thursday Feb 25th, in Wallberg 144. We still need volunteers for food for this and future weeks. Please contact me if you are interested.
nishi@ai.toronto.edu (Naomi Nishimura) (02/26/88)
I am still looking for speakers for this term. Please volunteer now, lest I opt to fill all the remaining time boring you about my thesis . . .
nishi@ai.toronto.edu (Naomi Nishimura) (02/29/88)
This week's speaker will be Teresa Przytycka, who will talk about parallel algorithms on trees and their application to graph problems. The meeting will be held in Wallberg 144 from 11:00-12:00 on Thursday, March 4. The talk will be based on two papers: "A Simple Parallel Tree Contraction Algorithm" by K.Abrahamson, N.Dadoun, D.Kirkpatrick, and T.Przytycka, and "Parallel Recognition of Complement Reducible Graphs and Cotree Contraction" by D.Kirkpatrick and T.Przytycka. The tree contraction problem is the problem of reducing a rooted tree to its root by a sequence of independent vertex removals. Parallel tree contraction may be considered as the base for many parallel algorithms on trees. In particular, it may be used for computing graph functions for those families of graphs which have tree representations.
nishi@csri.toronto.edu (Naomi Nishimura) (03/07/88)
This week's speaker will be Richard Cleve. He will be speaking on "A Model of Reversible Computation and its Applications." The meeting will be held in Wallberg 144 from 11:00-12:00 on Thursday, March 10. The following is Richard's description of his talk. This will be a practice of my interview talk. I'm hoping to get constructive criticism from the people who are present at Thursday's seminar. We introduce a model of computation which is reversible in a strong sense. Using the setting of this model, we prove that any log-depth algebraic formula can be evaluated by a straight-line program which uses a constant number of registers. This can be viewed as an extension of a result of Barrington about Boolean formulas to general algebraic formulas. We also observe that programs in our reversible model of computation correspond to a special class of block ciphers (which includes the Data Encryption Standard). We prove that if it is possible to generate pseudo- random functions that are in a complexity class called "DET" (slightly stronger than nondeterministic-log-space) then it is possible to generate polynomial-length block ciphers in this special class which are secure. Finally, we relate our reversible model of computation to that of Bennett, who considers reversibility as a way of reducing the thermodynamic cost of computation.
nishi@csri.toronto.edu (Naomi Nishimura) (03/08/88)
We still need volunteers to speak at seminar meetings later this term, with the first empty slot being next week. Please let me know as soon as possible if you are willing to speak (nishi@theory).
nishi@csri.toronto.edu (Naomi Nishimura) (03/14/88)
This week's speaker will be Philippe Derome, who will discuss the topic
``How to search fast a multikey table with no pointers.''
The meeting will be held in Wallberg 144 from 11:00-12:00
on Thursday, March 17.
This talk is a presentation of a paper to be published in STOC 88 by
Fiat, Naor, Sch\"{a}ffer, Schmidt, and Siegel. The data structure is an array
of n records with k keys. The queries specify the value of one key,
and the algorithm returns the record, if found, in O(log n), where the
constant is cklog k and c is independent of k and n. If m records
satisfy the query, the algorithm finds them in O(tlog n).
Please note that we still need a volunteer for food this Thursday, plus
volunteers for both speakers and feeders in some subsequent weeks. Let me
know when you are willing to volunteer . . .nishi@csri.toronto.edu (Naomi Nishimura) (03/20/88)
This week's speaker will be Dan Simon. The meeting will be held in Wallberg 144 from 11:00-12:00 on Thursday, March 24. Dan says: I plan to discuss "The Complexity of Perfect Zero Knowledge" by L. Fortnow. The result in this paper is that the complement of any perfect (or almost perfect) zero-knowledge language has a short interactive proof. Don't worry --I will be spending the first part of the talk explaining what interactive proofs and zero knowledge are, for those who have never seen them before (or who have but didn't bother to listen). This paper gives me the opportunity to discuss a variety of results and issues related to zero knowledge, the number and depth of which will depend on time constraints, general audience enthusiasm (snicker) and the quality of food provided by the designated feeder. Any volunteers for designated feeder? Please let me know (nishi@theory).
nishi@ai.toronto.edu (Naomi Nishimura) (03/25/88)
We still need a volunteer to speak this coming Thursday (March 31), and at least one more for subsequent weeks in the term. Please inform me (nishi@theory) immediately if you are willing. Prabhakar and I have offered to provide food next week, but only if there is a speaker. The offer will be retracted if there has been no volunteer by early next week.
nishi@csri.toronto.edu (Naomi Nishimura) (03/29/88)
Since no one volunteered to speak this week, there will be no meeting. If you can be convinced to speak in one of the next few weeks, please let me know.
nishi@csri.toronto.edu (Naomi Nishimura) (03/31/88)
Contrary to popular belief, there WILL be a student seminar next week, Thursday April 7. The speaker will be Toni Pitassi; the title will be announced early next week. No one else has volunteered to speak for the rest of the term. Please inform me immediately if you plan to do so. If there are no more volunteers, I suggest that we meet on April 14 to choose a seminar coordinator for the upcoming term.
toni@ai.toronto.edu (Toniann Pitassi) (04/06/88)
The student seminar will be held as usual on Thursday from 11-12 Toni Pitassi will be speaking. A proof system P1 is said to "p-simulate" another proof system P2 if there exists a uniform function computable in polytime which "translates" a proof in P2 of some formula, f, to a proof in P1 of the same formula f. The simulation is said to be "efficient" if the transformation produces a proof in P1 that is bounded by a polynomial in the length of the proof in P2. I will describe most of the major proof systems for propositional calculus and then classify them according to known p-simulation results. Recent lower bound and p-simulation results will then be given for resolution (and hopefully at least one proved).
nishi@csri.toronto.edu (Naomi Nishimura) (04/08/88)
If the message I tried to post yesterday got through, please ignore this message. Otherwise, pay close attention! To the best of my knowledge, there will be no more seminar meetings this term (if you wish to contest this claim by volunteering to speak, by all means do so). We need to coerce someone to be the seminar coordinator for next term. If all else fails, I can continue to disorganize the meetings. Since at that time I will be living out of town, it is likely that I won't be coming in to school or reading my mail on a daily basis. Consequently, it would make a lot more sense for someone else to take over. If you are interested in this task, please let me know. If more than one person volunteers, I'll solicit votes. I'll arbitrarily choose next Friday as a deadline for volunteering; if you oppose this rash act, let me know and I may be convinced to lengthen the campaign time.
bmkapron@ai.utoronto.ca (Bruce Kapron) (09/14/88)
The theory student seminar is a (hopefully) weekly meeting for theory students; volunteers present talks on any material of interest to them. All theory students are encouraged to attend. In order to establish a suitable time for the seminar, I need to know when people are available. If you have not obtained a scheduling form from me yet, please do so (they are availble on the door of SF3208). Return the forms to me as soon as possible. WE NEED VOLUNTEERS!! If you are interested in giving a talk, please let me know. Bruce Kapron bmkapron@theory
bmkapron@ai.utoronto.ca (Bruce Kapron) (09/21/88)
I have received about 23 scheduling forms; Tuesday from 2:00-4:00 and Thursday from 2:00-3:00 remain as available time slots. Since the other theory seminar is Thursday 3:00-4:00, the Tuesday time slot seems preferable. Anyone who objects to the seminar in this time period should let me know as soon as possible (say, before Thursday at 4:00pm), so that I can try to get a room. Bruce Kapron bmkapron@theory
bmkapron@ai.utoronto.ca (Bruce Kapron) (09/27/88)
The powers that be say that many people want rooms and so we will just have to wait our turn. Hence there will be no meeting of the student seminar this week. I am sure, however, that we will manage to get something for next week. Bruce Kapron bmkapron@theory
bmkapron@ai.utoronto.ca (Bruce Kapron) (09/30/88)
It is very likely that there will be a meeting of the theory student seminar on Tuesday, October 4 at 2pm. The location will be University College, room 257. To get to this room, you must use the stairway inside the large doors on the east side of the building, i.e. the so-called `dragon' stairs (no debates, please, on whether it is a dragon or a gryphon). An announcement regarding the speaker and topic should appear in this newsgroup in the near future. Bruce Kapron bmkapron@theory
bmkapron@ai.utoronto.ca (Bruce Kapron) (10/03/88)
There will be a meeting of the student seminar this Tuesday at 2pm in University College Room 257. Steve Bellantoni will give a talk on "An Adversary Argument". He will present a proof for the PRAM model of computation, and will try to (a) convey the basic idea of an adversary argument and (b) introduce subjects of research for the PRAM model. See my previous posting regarding the location of the seminar. Bruce Kapron bmkapron@theory
bmkapron@ai.utoronto.ca (Bruce Kapron) (10/07/88)
Tuesday, October 11, 2:30pm at University College Room 257. Mark Giesbrecht will be giving a talk on a subject related to factoring integers. More details will be forthcoming in the near future. NEW STUDENTS: We would really like to see you there. I will post a map on the door of my office (SF3208) for the benefit of anyone who isn't sure of how to get to UC257. Bruce Kapron bmkapron@theory
bmkapron@ai.utoronto.ca (Bruce Kapron) (10/14/88)
Time: Tuesday, October 18, 2:00pm (i.e., 1400h) Location: University College Room 257 Speaker: Steve Rudich Topic: To be announced Bruce Kapron bmkapron@theory
bmkapron@ai.utoronto.ca (Bruce Kapron) (10/15/88)
As mentioned previously, Steven Rudich will be speaking at the next meeting of the student seminar on October 18. Title: Of dice and coins... This talk will explore the problem of simulating the roll of an n-sided die, by a bounded number of flips of a small set of biased coins. The talk is designed to be fun and easy to understand. It requires nothing beyond high school math. A natural (still open) question results.
bmkapron@ai.utoronto.ca (Bruce Kapron) (10/21/88)
There will be no student seminar this week, as many of us will be at FOCS. Bruce Kapron bmkapron@theory
bmkapron@ai.utoronto.ca (Bruce Kapron) (10/31/88)
Time: Tuesday, November 1, 2:00pm EST
Location: University College Room 257
Speaker: Murray Sherk
Title: A Survey of Multi-dimensional Date Structures and Related Issues
Summary:
-find out how to take any static data structure and turn it into
one allowing insertions and deletions
-no specific prior knowledge requiredbmkapron@ai.utoronto.ca (Bruce Kapron) (11/04/88)
Time: Tuesday, November 8, 2pm EST Location: University College Room 257 Speaker: Naomi Nishimura Title: Parallel Computation on 2-3 Trees Summary: This talk will be based on a paper by Paul, Vishkin, and Wagener, and will touch upon issues concerning data structures and parallel algorithms. Consider the following problem: k processors of a PRAM simultaneously insert, delete, or access data stored in a 2-3 tree. Clearly, if we allow concurrent read, then simultaneous access can be done in time log(number of data items). But what about insertion and deletion, and what about other PRAM models? We will solve this problem, relying on the paper only where necessary. This means that I will guide the discussion, as needed, and you will figure out the results. No previous experience with either 2-3 trees or PRAMs is necessary.
bmkapron@theory.utoronto.ca (Bruce Kapron) (11/11/88)
Time: Tuesday, November 15, 2pm EST Location: University College Room 257 Speaker: Andrew Malton Summary: An informal introduction to the ideas of constructive logic will be given from the point of view of programming methodology. The presentation will be based on R. Constable's ``Semantics of Evidence''.
bmkapron@theory.utoronto.ca (Bruce Kapron) (11/17/88)
There have been several requests to have the seminar announced by mail. As far as I know, there is no ``official'' mailing list for theory people. I have constructed a list from /etc/groups. If you wish to receive seminar announcements by mail and are not on the list, please let me know. Time: Tuesday, November 22, 2pm EST Location: University College Rm. 257 Speaker: Toni Pitassi Summary: This week we will look at a modified version of Armin Haken's superpolynomial lower bound on the size of resolution proofs. In contrast with Armin's proof which relies on counting, this proof is adversarial (ie. feasibly constructive) in that we give a (polynomial) algorithm which finds a contradiction when given an alleged short proof of the propositional pigeon-hole principle. If time permits, we will see from this analysis when generalized versions of the pigeon-hole principle can and cannot yield superpolynomial lower bounds using the same technique (and why this is interesting). Lastly, I'll try to fit these results into the bigger complexity theoretic picture.
bmkapron@theory.utoronto.ca (Bruce Kapron) (11/28/88)
Time: Tuesday, November 29, 2pm EST Location: University College Rm. 257 Speaker: Jim McInnes Summary: Jim will present a recent result of Mike Luby showing how to obtain a pseudo-random number generator from any one-way function.
bmkapron@theory.utoronto.ca (Bruce Kapron) (12/21/88)
Scheduling forms for next term are available on the door of my office (SF3208). Please complete one and put it in my mailbox or on my desk. Thanks. Bruce
bmkapron@theory.utoronto.ca (Bruce Kapron) (01/11/89)
According to the timetables that I have received, there are no times which are suitable for everyone. Of the slots with only one `-', Monday at 3:00pm has the most `+' 's, so I guess it wins unless someone has serious objections. Please let me know if you do. Bruce
bmkapron@theory.utoronto.ca (Bruce Kapron) (01/13/89)
It looks like Tues at 3pm is the only available time slot, despite its drawbacks. It is possible that there may be a meeting next week. Location and speaker to be announced. Bruce
bmkapron@theory.utoronto.ca (Bruce Kapron) (02/04/89)
Date : Tuesday, February 7, 1989, 3pm Location : GB420 Speaker: Wayne Eberly Summary: Wayne will be doing a run-through for his official seminar on Thursday. The material will probably be the same; the presentation here will be less formal.
bmkapron@theory.utoronto.ca (Bruce Kapron) (03/27/89)
Once again, Arvind's talk will be postponed for a week. This week, Andrew Malton will be presenting his ``interview'' talk. Time: Tuesday, March 28, 3pm Location: GB420 Title: A Type-Theoretic Explanation of Program Derivation Description: Looking at the actual requirements of specification, and the need to be able to complain when an implementation fails, I use an idea of Godel to define specification, implementation, and complaint. The result is a new interpretation of program specification connectives. I then sketch how ordinary proofs of correctness (in Hoare's Logic) represent implementations of such specifications.
bmkapron@theory.utoronto.ca (Bruce Kapron) (04/10/89)
Time: Tuesday, April 11, 3pm EDT Location: GB420 Speaker: Arvind Gupta Arvind will continue his talk on the Paris-Harrington result. NOTE: If Neil Robertson decides to present something at this time, the student seminar will be cancelled.
bmkapron@theory.utoronto.ca (Bruce Kapron) (08/03/89)
Would someone please volunteer to organise the student seminar for 1989/90. Thank you. Bruce Kapron bmkapron@theory.utoronto.ca