CS 860: Space Bounded Computation (Winter 2026)

Lectures	Tuesdays, 11:30 AM - 2:20PM in Davis Center (DC) 2568
Instructor	Sepehr Assadi        (userid: sassadi)
Instructor office hours	By appointment
Prerequisites	Mathematical maturity, and a strong background in undergraduate-level probability theory, data structures, and algorithm design are all essential.
Textbook	There is no official textbook. Lecture notes and other required materials will be posted on this webpage.
Course outline	The course outline will be posted here at some point before the start of the term. This page contains the highlights of course outline that can be updated as the term progresses.
Communication	The lectures will be delivered on the blackboard. We use LEARN for assignments and grades. For specific concerns, questions, or comments regarding your experience in the course, you can directly email me @ (sassadi).

Grading

The final grade for the course will be based on the following weights:

• 50% Participation and Discussions
• 50% Scribe notes

Course Calendar

The schedule below the red line is tentative and subject to change (including potentially the release and due dates for assignments).

#	Date	Topics	Lecture notes & References	Scribe
1	Tuesday January 6	Background: Models of computation, Basic Tools, Barrington's Theorem	[lec1], B89, BC92	--
*	Tuesday January 13	No class: A make-up class will be scheduled later
2	Tuesday January 20	Tree Evaluation, Simulating Time with Space	[lec2], CM24, G25, W25	--
3	Tuesday January 27	Undirected Connectivity in Logspace	R02, RV05	--
4	Tuesday February 3	Savitch's Theorem and Directed Reachability in Sublinear Space	[lec4], S70, BBRS98	--
5	Tuesday February 10	(Node-Named) Jumping Automata on Graphs: Lower Bound for Savitch's Theorem	[lec5], P93	Gunadi Gani
*	Tuesday February 17	No class: Reading Week
6	Tuesday February 24	Time-Space Tradeoffs on Branching Programs I: Uniques, Matrix Multiplication	[lec6], A86, B91	Max Jiang
7	Tuesday March 3	Time-Space Tradeoffs on Branching Programs II: Decision Problems	[lec7], BSSV03	Peter Matsakis
8	Tuesday March 10	Time-Space Tradeoffs on Branching Programs III: The Random-Query Model	[lec8], RZ20, D24	Daniel Jiang
8	Tuesday March 17	Time-Space Tradeoffs on Branching Programs IV: Learning Theory Problems	R16, R17	Aryan Vahabpour
10	Tuesday March 24	Randomness in Small Space: Nisan's PRG	N90	Dunyang Ni
11	Friday* March 27	Randomness in Small Space: Saks-Zhou's Theorem	SZ95	Helia Yazdanyar
12	Tuesday March 31	Non-determinism in Small Space: NL=co-NL, Uniform Time-Space Tradeoffs	I88, S88, FLMV05	Gunadi Gani

Resources

There is no official textbook for the course (most of our material is not in textbooks yet anyway). The following resources are all optional but they can be quite helpful and I encourage you to refer to them throughout the term for more details on the topics we cover in the class.

Further Reading

For some related textbooks and surveys, you can refer to:

V25	Emanuele Viola, Mathematics of the Impossible: The Complexity of Computation. © Copyright 2023-2025 Emanuele Viola.

Bibliography

This is a (rather incomprehensive) list of the papers related to the topics discussed in the lectures. The list will be updated frequently throughout the term.

A86	Karl Abrahamson. Time-Space Tradeoffs For Branching Programs Contrasted With Those For Straight-Line Programs. FOCS 1986.
BBRS98	Greg Barnes, Jonathan F. Buss, Walter L. Ruzzo, Baruch Schieber. A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity. SICOMP 1998.
B89	David A. Mix Barrington. Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC1. J. Comput. Syst. Sci 1989.
B91	Paul Beame. A General Sequential Time-Space Tradeoff for Finding Unique Elements. STOC 1989 and SICOMP 1991.
BSSV03	Paul Beame, Michael Saks, Xiaodong Sun, Erik Vee. Time-space trade-off lower bounds for randomized computation of decision problems. FOCS 2000 and JACM 2003.
BC92	Michael Ben-Or and Richard Cleve. Computing Algebraic Formulas Using a Constant Number of Registers. STOC 1988 and SICOMP 1992.
CM24	James Cook and Ian Mertz. Tree Evaluation is In Space O(log n * log log n). STOC 2024 and SICOMP 2025.
D24	Itai Dinur. Time-Space Lower Bounds for Bounded-Error Computation in the Random-Query Model. SODA 2024.
FLMV05	Lance Fortnow, Richard Lipton, Dieter van Melkebeek, Anastasios Viglas. Time-Space Lower Bounds for Satisfiability. JACM 2005.
I88	Neil Immerman. Nondeterministic space is closed under complementation. SICOMP 1988.
G25	Oded Goldreich. On the Cook-Mertz Tree Evaluation Procedure. Computational Complexity and Local Algorithms 2025.
N90	Noam Nisan. Pseudorandom generators for space-bounded computation.. STOC 1990 and Combinatorica 1992.
R02	Omer Reingold. Undirected ST-Connectivity in Log-Space. STOC 2002.
R16	Ran Raz. Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning. FOCS 2016 and JACM 2019.
R17	Ran Raz. A Time-Space Lower Bound for a Large Class of Learning Problems. FOCS 2017.
RV05	Eyal Rozenman and Salil P. Vadhan. Derandomized Squaring of Graphs. APPROX-RANDOM 2005.
RZ20	Ran Raz and Wei Zhan. The Random-Query Model and the Memory-Bounded Coupon Collector. ITCS 2020.
P93	C. K. Poon. Space bounds for graph connectivity problems on node-named JAGs and node-ordered JAGs. FOCS 1993.
S70	Walter J Savitch. Relationships between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci 1970.
S88	Robert Szelepcsenyi. The method of forced enumeration for nondeterministic automata. Acta Informatica 1988.
SZ95	Michael Saks and Shiyu Zhou. BPSACE(S) \subseteq DSPACE(S^3/2). FOCS 1995 and J. Comput. System. Sci 1999.
W25	Ryan Williams. Simulating Time with Square-Root Space. STOC 2025.

Resources on LaTeX

You can download LaTeX for free. For the purpose of this course, you do not even need to install LaTeX and can instead use an online LaTeX editor such as Overleaf.

Two great introductory resources for LaTeX are Getting started with TeX, LaTeX, and friends by Allin Cottrell (for general purpose LaTeX) and LaTeX for Undergraduates by Jim Hefferon (for undergraduates mathematics) accompanied by the following cheatsheet. You can also use this wonderful tool Detexify by Daniel Kirsch for finding the LaTeX commands of a symbol (just draw the symbol!).

If you are interested in learning more about LaTeX (beyond what is needed for this course), check the Wikibook on LaTeX and the Wikibook on LaTeX for Mathematics.

Policies and Statements

Territorial Acknowledgement

The University of Waterloo acknowledges that much of our work takes place on the traditional territory of the Neutral, Anishinaabeg and Haudenosaunee peoples. Our main campus is situated on the Haldimand Tract, the land granted to the Six Nations that includes six miles on each side of the Grand River. Our active work toward reconciliation takes place across our campuses through research, learning, teaching, and community building, and is co-ordinated within the Office of Indigenous Relations.

Email Policy

Email is fast and tends to give the illusion of constant and immediate access. But that cannot realistically happen. I am available to you in general during this course via email but it may take up 24 hours (48 hours over the weekends) before you hear back from me. Also, please use email only to communicate specific concerns, questions, or comments regarding your experience in the course, or setting up appointments for in-person meetings outside office hours in case necessary. Questions directly related to the materials of the course and clarifications about lectures should be posted on Piazza or discussed during office hours instead.

Important note: Please start the subject of all your emails in this course with '[CS860-W26]' (like "[CS860-W26] discuss my final grade") -- I am using bunch of different email filters to manage my (unmanageable) inbox and I may not get to see emails without this format at all and there is no guarantee on response time for such emails.

Students with Disabilities

You are encouraged to discuss with me any appropriate accommodations that we might make on your behalf following the guidelines of the AccessAbility Services.

AccessAbility Services, located in Needles Hall, Room 1401, collaborates with all academic departments/schools to arrange appropriate accommodations for students with disabilities without compromising the academic integrity of the curriculum. If you require academic accommodations to lessen the impact of your disability, please register with AccessAbility Services at the beginning of each academic term.

Statement of Inclusivity

I am committed to creating a learning environment in which all of my students feel safe and included, regardless of race, ethnicity, religion, gender or sexual orientation. Because we are individuals with varying needs, I rely on your feedback to achieve this goal. I invite you to let me know about what I can stop, start, or continue doing to make sure every one of my students feels valued and can engage actively in our learning community.

Faculty of Math Statement on Diversity: It is our intent that students from all diverse backgrounds and perspectives be well served by this course, and that students’ learning needs be addressed both in and out of class. We recognize the immense value of the diversity in identities, perspectives, and contributions that students bring, and the benefit it has on our educational environment. Your suggestions are encouraged and appreciated. Please let us know ways to improve the effectiveness of the course for you personally or for other students or student groups. In particular:

• We will gladly honour your request to address you by an alternate/preferred name or gender pronoun. Please advise us of this preference early in the term so we may make appropriate changes to our records.
• We will honour your religious holidays and celebrations. Please inform us of these at the start of the course.
• We will follow AccessAbility Services guidelines and protocols on how to best support students with different learning needs.

Your Health & Well-Being

This is a challenging course with various advanced topics and not-so-easy assignments and exams. All of these are going to be time and energy consuming. But, this is also an elective course so one of my main goals is for you to enjoy taking this course and learning these cool materials as much as I enjoy teaching them. Part of making sure you have fun involves taking care of yourself. Do your best to maintain a healthy lifestyle and work-life balance this term by eating well, exercising, getting enough sleep, and taking some time to relax -- all of these will tremendously help you to achieve your goals in the course and to enjoy the process in the meantime.

You can find more resources to help you with your health & well-being with the Campus Wellness and Student Success Office -- they have tons of resources on helping you to succeed, including very good tips on time management techniques.

Faculty of Math Statement on Mental Health: The Faculty of Math encourages students to seek out mental health support if needed:

On-campus Resources:

• Campus Wellness: here to help enhance and support your wellness in a safe, respectful, and inclusive environment.
• Counselling Services: email counselling.services@uwaterloo.ca or phone 519-888-4567 ext. 32655
• MATES: one-to-one peer support program offered by Waterloo Undergraduate Student Association (WUSA) and Counselling Services: mates@wusa.ca
• Health Services: located across the creek from the Student Life Centre; phone: 519-888-4096.

Off-campus Resources:

• Good2Talk (24/7): Free confidential help line for post-secondary students. Phone: 1-866-925-5454 (Ontario and Nova Scotia only)
• Here 24/7: Mental Health and Crisis Service Team. Phone: 1-844-437-3247 (Waterloo Region only)
• OK2BME: set of support services for lesbian, gay, bisexual, transgender, or questioning teens. Phone: 519-884-0000 extension 213 (Waterloo Region only)
• EMPOWER ME: Phone 1-833-628-5589 for Cdn./USA; for other countries see here
• EMPOWER ME in China: China North 108007142831 and China South 108001402851

Rights and Responsibilities

Every member of this class---instructor, TA, and students---has rights and responsibilities toward having a pleasant, fair, supportive, and free of discrimination and micro-aggression environment in this course, and we are all answerable to the University policies governing ethical behaviour (Policy 33).

In addition, academic dishonesty and plagiarism is considered a serious offense in this course. I expect that any assignment or exam you submit in this course will be your own product and follows the collaboration and external resources policies specified in the course outline. If an assignment is too hard, start earlier, ask for help, or simply do not answer the question --- academic dishonesty is never the right answer. If you have any concerns or questions about these policies, please discuss them with me.

Finally, a reminder that all the course content including lecture notes, presentations, and other materials prepared for the course, are the intellectual property (IP) of the instructor. These course materials are available to you to enhance your educational experience, and sharing them without permission and proper citation is a violation of intellectual property rights.

University Policies: It is your job to know the university policies that govern your behaviour in this course. Some pointers are:

• Academic Integrity: In order to maintain a culture of academic integrity, members of the University of Waterloo community are expected to promote honesty, trust, fairness, respect and responsibility. All members of the UW community are expected to hold to the highest standard of academic integrity in their studies, teaching, and research. The Office of Academic Integrity's website contains detailed information on UW policy for students and faculty. This site explains why academic integrity is important and how students can avoid academic misconduct. It also identifies resources available on campus for students and faculty to help achieve academic integrity in---and out---of the classroom.


• Grievance: A student who believes that a decision affecting some aspect of their university life has been unfair or unreasonable may have grounds for initiating a grievance (Policy 70). When in doubt please be certain to contact the department/school’s administrative assistant who will provide further assistance.


• Discipline: A student is expected to know what constitutes academic integrity to avoid committing academic offences and to take responsibility for their actions. A student who is unsure whether an action constitutes an offence, or who needs help in learning how to avoid offences (e.g., plagiarism, cheating) or about "rules" for group work/collaboration should seek guidance from the course professor, academic advisor, or the undergraduate associate dean.
  For information on categories of offences and types of penalties, students should refer to Policy 71. For typical penalties check Guidelines for the Assessment of Penalties.


• Appeals: A decision made or penalty imposed under Policy 70, Student Petitions and Grievances (other than a petition) or Policy 71, Student Discipline may be appealed if there is a ground. A student who believes they have a ground for an appeal should refer to Policy 72, Student Appeals.

Intellectual Property: Students should be aware that this course contains the intellectual property of their instructor, TA, and/or the University of Waterloo. Intellectual property includes items such as:

• Lecture content, spoken and written (and any audio/video recording thereof);
• Lecture handouts, presentations, and other materials prepared for the course (e.g., PowerPoint slides);
• Questions or solution sets from various types of assessments (e.g., assignments, quizzes, tests, final exams); and
• Work protected by copyright (e.g., any work authored by the instructor or TA or used by the instructor or TA with permission of the copyright owner).

Course materials and the intellectual property contained therein, are used to enhance a student's educational experience. However, sharing this intellectual property without the intellectual property owner's permission is a violation of intellectual property rights. For this reason, it is necessary to ask the instructor, TA and/or the University of Waterloo for permission before uploading and sharing the intellectual property of others online (e.g., to an online repository).

Permission from an instructor, TA or the University is also necessary before sharing the intellectual property of others from completed courses with students taking the same/similar courses in subsequent terms/years. In many cases, instructors might be happy to allow distribution of certain materials. However, doing so without expressed permission is considered a violation of intellectual property rights.

Please alert the instructor if you become aware of intellectual property belonging to others (past or present) circulating, either through the student body or online. The intellectual property rights owner deserves to know (and may have already given their consent).

Use of Generative Artificial Intelligence: The following statement is prepared by the Office of Academic Integrity with input from the Centre for Teaching Excellence, Library, and consultations with Associate Deans and members of the Standing Committee on New Technologies, Pedagogy, and Academic Integrity (Last Updated: August 2023):

Generative artificial intelligence (GenAI) trained using large language models (LLM) or other methods to produce text, images, music, or code, like Chat GPT, DALL-E, or GitHub CoPilot, may be used for assignments in this class with proper documentation, citation, and acknowledgement. Recommendations for how to cite GenAI in student work at the University of Waterloo may be found through the Library.

Please be aware that generative AI is known to falsify references to other work and may fabricate facts and inaccurately express ideas. GenAI generates content based on the input of other human authors and may therefore contain inaccuracies or reflect biases. In addition, you should be aware that the legal/copyright status of generative AI inputs and outputs is unclear. Exercise caution when using large portions of content from AI sources, especially images. More information is available from the Copyright Advisory Committee.

You are accountable for the content and accuracy of all work you submit in this class, including any supported by generative AI.

---