Remote teaching on gather.town

By Jason Hartline and Aravindan Vijayaraghavan, Northwestern University.

Screenshot from the podium of our gather.town classroom.

Due to the pandemic, Northwestern computer science courses for the Fall of 2020 were taught remotely. We co-taught our undergraduate Theory of Computation course in a flipped format on gather.town. It was a fantastic experience. Class time was much more interactive than the Zoom classes we had both taught previously. Also, the students liked that they could interact with other students, and the change (versus yet another Zoom class). It went well and we plan to repeat the experience with our winter courses.

The rough details are as follows.

Flipped-class format

The course was taught in the flipped-class format. We had pre-recorded lectures that the students had to watch before each class. Class time, on the other hand, was spent discussing concepts and working through exercises in small groups.

Videos and Exercises

The model for pre-recorded video was three 15-minute videos, though in practice it was more often two 30-minute videos. Each video had accompanying exercises (implemented using the Canvas Quiz feature). It was recommended for students to interleave the exercise questions with the videos as some exercises were designed to reinforce concepts so as to make subsequent videos easier to understand. They were encouraged to work together on these exercises.

Class on Gather.town

The class time was entirely on Gather.town. The classroom was organized with cabaret seating layout. Students virtually sat at four-person tables (though the capacity was not a hard limit). We gave presentations from a podium at the front of the room and students could ask questions from microphones in the middle of the room. Both the tables and the podium and microphone were enabled by gather.town video chat.

replica of our classroom is available for self-guided tours. It is recommended to bring a colleague. This classroom was provided to us for beta-testing by virtualchair.net and similar ones are now available from them or you can build your own on gather.town. (Full disclosure: Jason Hartline is a cofounder of virtualchair.net.)

The 80-minute class time was split into two parts. The first half of the class comprised a recap of concepts from the videos and related discussion, and the second half had the students working in groups on a homework-style problem.

Class Part I: Discussion

For the class discussion, we started with a slide of 5-6 discussion questions. This slide was screen-shared from a podium in the virtual classroom. As students joined the class they were encouraged to begin discussing these questions with other students at their tables. After ten minutes we led a discussion of the questions at the podium, encouraging students to chime in with answers from their discussion groups. Our virtual classroom had two microphones among the cabaret seats that students could use to address the class. We also encouraged students to bring up any questions they had.

This part of the class was quite interactive, and it would also give us a sense of how well the students understood the material, and enabled us to reemphasize material accordingly.

Class Part II: Problem Solving

The second half of class was reserved for student problem solving in groups (at their tables). During the problem-solving session we would join tables of students to answer questions, help talk them through issues, and ensure that they were making progress.

Other virtual interactions

The gather.town space had two additional rooms: a study hall and an office hours room. The study hall featured shared whiteboards and was a place where students could meet up for discussions and group work (homework problems were assigned to students in groups of two). The course staff conducted office hours in the office hours room.

Meeting on gather.town was very convenient and meetings of the course staff were also conducted in the virtual office.

Video content in watch parties.

We scheduled video content to be played in watch parties for students to view together the night before class. However, perhaps due to initial technical difficulties, this feature was not utilized by the students.

Difficulties

The following were the main difficulties we encountered. (Configuring the space was fairly easy with the virtualchair.net automation.)

  1. It was slightly awkward that we could not leave our screenshare at the podium at the same time as we joined group discussions at the tables. This could be addressed by logging into gather.town twice and using one login for screensharing and the other for discussions with students.
  2. We did not establish a video-on policy and we regret it. While we wanted to respect student privacy, students should be fully engaged in discussions and full engagement warrants videos being on. Moreover, we attempted to grade student participation, but it was difficult to know who is talking when many of the students had their video off.
  3. Gather.town does not have a simple mechanism for keeping track of participation of students. Our process was manual and difficult.

Student Feedback

The following quotes from student the student course evaluations that pertain to the flipped format and remote technology. Students were generally quite positive.

  • “The flipped format worked really well for this material; it was really valuable to be able to discuss practice exercises with our peers during class.”

  • “Gather.town was a fantastic choice and made me really look forward to attending this class online. Getting to talk and solve problems with teammates really helped me consolidate ideas. (And it was also really nice to be able to socialize a bit.) The flipped classroom style worked really well.”

  • “After the first few weeks, this was certainty my best class in terms of adapting to remote; gather.town discussions were really great (so great my table often stayed after class to continue them!)”

  • “I thought that the gather.town format was an excellent decision. Being able to discuss course topics with other students in the class definitely helped me consolidate ideas. The recorded video lectures were high quality, and the professors both did a great job leading discussion in class.”

  • “It was done on gather.town, which was a bit rocky the first few weeks but got better by the end; really enjoyed discussing with other people about the exercises (wish more time was spent on them actually).”

  • “The practice exercises with our peers were really helpful. Most of the video lectures were clear enough, but being able to discuss points of confusion with classmates was a great way to clear up questions.”

Conclusions

Overall it was a fantastic experience that we are looking to refine in subsequent course offerings. Our virtual gather.town space was for our class only, but it would be natural to use the same space for multiple classes offered within the same department and doing so might encourage more student meetings on the platform. Our idea of watch parties for students to watch videos together needs further adjustments and testing.

Northwestern papers at FOCS 2020

The Northwestern CS Theory group had three papers at the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2020), which was recently held virtually.

Northwestern Economics PhD student Modibo Camara, CS PhD student Aleck Johnsen, and Prof. Jason Hartline co-authored a paper “Mechanisms for a No-Regret Agent: Beyond the Common Prior“.  The paper analyzes a broad class of Principal-Agent games in economics that normally depend on common knowledge of a precise distribution over an unknown, payoff-relevant input, using instead online learning in repeated game play.  A key idea of the paper which describes (possibly externally-informed) Agents behaviorally with only a no-regret property is to extend previous definitions for “regret” to consider counterfactual sequences of the repeated play. Link to the talk.

Northwestern CS PhD students Yingkai Li and Aleck Johnsen, and Prof. Jason Hartline co-authored a paper “Benchmark Design and Prior Independent Optimization“.  The paper introduces a formal approach to the study of benchmark design, as a parameter of worst case algorithm design to be optimized.  Incorporating first economic properties to justify and measure benchmarks, the main result of the paper shows that benchmark design is equivalent to algorithm design when inputs are drawn independently from a common-but-unknown distribution.  Another main result solves a longstanding open question in 2-agent revenue auction design, which further serves as application for the benchmark design result. Link to the talk.

Prof. Aravindan Vijayaraghavan co-authored a paper “Scheduling Precedence-Constrained Jobs on Related Machines with Communication Delay” with Biswaroop Maiti (Northeastern), Rajmohan Rajaraman (Northeastern), David Stalfa (Northeastern), and Zoya Svitkina (Google). The paper studies the problem of scheduling n precedence-constrained jobs on m uniformly-related machines in the challenging setting where we have to account for communication delays. Communication delay is the amount of time that must pass between the completion of a job on one machine and the start of any successor of that job on a different machine. The paper shows both algorithmic results and lower bounds. This includes the first polylogarithmic factor approximation algorithm for this problem, superconstant integrality gaps, and bounding the advantage of duplication in these settings. Link to the talk.

Seeking nominations for 2020 Junior Theorists Workshop

We are seeking nominations for outstanding final-year Ph.D. students or postdocs to present their recent research at the 2020 Junior Theorists Workshop on December 17 and 18. The workshop will visit broad themes in theoretical computer science and we expect to invite eight speakers. Due to the pandemic, the workshop will be virtual this year.

If you would like to nominate an outstanding student or postdoc from your institution, please submit the paper (URL or pdf) the speaker would likely present and a brief nomination statement here by Nov. 30. If you already have a letter of recommendation for the nominee that includes a discussion of the paper, that would be sufficient. Nomination letters will be kept in confidence. There is no need to check the availability and interest of the nominee before nominating.

We anticipate receiving more nominations than we can accept and will consider merit, breadth, diversity, and random coins in determining the program. In particular, we regret that the workshop will probably not be able to accommodate all outstanding nominees.

The Junior Theorists Workshop is part of our Quarterly Theory Workshop series and is in its third year. Details about last year’s Junior Theorists Workshop and other workshops in the Quarterly Theory Workshop series can be found on the events page.

NSF funds Institute for Data, Econometrics, Algorithms, and Learning

As part of the HDR TRIPODS program, NSF has funded the Institute for Data, Econometrics, Algorithms, and Learning (IDEAL).  The institute is codirected by Prof. Hartline and Prof. Vijayaraghavan with key programs being organized also by Prof. Khuller and Prof. Makarychev.  It is a collaboration between Northwestern, Toyota Technology Institute, and University of Chicago bridges faculty in CS, Economics, Statistics, Electrical Engineering, and Operations Research.   See the news release by McCormick.

New additions to Theory group

The Northwestern Theory group is excited to announce that we have several folks joining us at the beginning of this academic year! We have Hedyeh Beyhaghi as a postdoc joining from Cornell, Shravas Rao as a postdoc joining from NYU, Sumedha Uniyal as a visiting postdoc from Aalto University, Finland; Pattara Sukprasert as a new grad student transferring from the University of Maryland College Park; Saba Ahmadi and Sheng Yang, visiting grad students from the University of Maryland College Park.

Hedyeh Beyhaghi. Dr. Beyhaghi’s research interests are in Algorithm Design, with an emphasis on Algorithmic Game Theory and Mechanism Design. Her research mainly focuses on Auction Design, Online Stochastic Optimization, and Matching Markets. She obtained her Ph.D. at Cornell University, under the supervision of Eva Tardos.This text is only to create extra space for good indentation. Kudos to you if you found this text! Have a nice day. This text is only to create extra space for good indentation. Kudos to you if you found this text! Have a nice day.

 

Shravas Rao. Dr. Rao’s research interests are in theoretical computer science, with an emphasis on derandomization and pseudorandomness. He completed his Ph.D. at New York University advised by Oded Regev.This text is only to create extra space for good indentation. Kudos to you if you found this text! Have a nice day. This text is only to create extra space for good indentation. Kudos to you if you found this text!

 

Sumedha Uniyal. Dr. Uniyal is a postdoctoral researcher (Oct’17-Present) in the group of Prof. Parinya Chalermsook at Aalto University, Finland. She did her Ph.D. (Apr’13-Oct’17) at IDSIA, University of Lugano, Switzerland; under the supervision of Prof. Fabrizio Grandoni. She is broadly interested in approximation algorithms and algorithmic graph theory. During her Ph.D., she has worked on developing approximation algorithms for connectivity problems, clustering problems, and submodular optimization. Recently, she is also interested in structural graph theory and its implications in algorithms. She will be a visiting scholar at Northwestern till Dec’19 working with Prof. Samir Khuller.

 

Pattara Sukprasert. Pattara is a third-year Ph.D. student advised by Prof. Samir Khuller. He transferred from the University of Maryland College Park, where he spent his first two Ph.D. years and received a Master’s degree. Before that, he lived mostly in Thailand and got another Master’s degree from Kasetsart University advised by Prof. Jittat Fakcharoenphol. He is interested in approximation algorithms and graph theory, and has worked on network design problems, network flow problems, and some structural graph theory problems. Recently, he has also developed some interests in fast (up to sub-cubic) approximation algorithms.

 

Saba Ahmadi. Saba is a fifth year PhD student at the University of Maryland College Park visiting Northwestern, and she is advised by Prof. Samir Khuller. She is mainly interested in designing approximation algorithms. She is also interested in the topic of fairness and its relevance to combinatorial optimization. She finds problems at the intersection of AI and combinatorial optimization very interesting, one example is how to have diversity in the matching markets.

 

Sheng Yang. Sheng is a fifth year PhD student at University of Maryland, College Park advised by Prof. Samir Khuller. Currently, he is visiting Northwestern as a pre-doctoral visiting scholar. He is broadly interested in approximation algorithms. He has worked on graph theory topics related to connected dominating set and induced subgraph counting. Currently, he is mainly working on various scheduling problems, classical and new challenges originating from cloud computing.

Northwestern CS Theory group @ FCRC 2019

The Northwestern CS Theory group cumulatively had eight papers at conferences held as part of the ACM Federated Computing Research Conference(FCRC) 2019, which took place recently in Phoenix, AZ. We had two papers in COLT, four in EC, and one each in SPAA and STOC. Members of the group who attended include Professors Jason Hartline, Samir Khuller, Konstantin Makarychev, and Aravindan Vijayaraghavan, postdoc Xue Chen, PhD students Yiding Feng, Aleck Johnsen, Yingkai Li, and Aravind Reddy. Also in attendance were CS Prof. Jessica Hullman and Econ PhD student Modibo Camara.

Conference on Learning Theory(COLT):

TCS postdoc Xue Chen presented a joint paper “Active Regression via Linear-Sample Sparsification” with Eric Price (UT Austin). This paper gives an efficient algorithm with an optimal sample complexity for the classical problem of linear regression. Its techniques yield improved results for the non-linear sparse Fourier transform setting.

TCS Ph.D. student Yingkai Li presented a joint paper with Yining Wang (CMU) and Yuan Zhou (UIUC). The paper “Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits” obtained almost tight dependence on the time horizon for regret minimization in linear bandits. One of the main results is to show that there is an extra sqrt(log T) factor in the lower bound, revealing a regret scaling quite different from classical multi-armed bandits. Our proof techniques include variable confidence levels and a careful analysis of layer sizes of SupLinUCB on the upper bound side, and delicately constructed adversarial sequences showing the tightness of elliptical potential lemmas on the lower bound side.

Economics and Computation(EC):

TCS Ph.D. alumnus Sam Taggart (Assist. Prof. Oberlin College) presented a joint paper with TCS Prof. Jason Hartline in the joint session of EC and STOC.  The paper, “Sample Complexity for Non-truthful Mechanisms“, describes a family of winner-pays-bid and all-pay (i.e., non-truthful) mechanisms that can be optimized from past bid data from the same market.  Most mechanisms in practice are non-truthful and, for example, the winner-pays-bid format is especially common.  The literature on sample complexity in mechanism design is well established, however, this paper is the first to consider non-truthful mechanisms.

TCS Prof. Jason Hartline presented a joint paper with TCS Ph.D. student Aleck Johnsen, Dennis Nekipelov (UVA), and Onno Zoeter (Booking.com).  The paper, “Dashboard Mechanisms for Online Marketplaces” gives a theoretical model for how a bidding dashboard can both make it easier for bidders in an online marketplace to optimize their bids and for the designer to optimize the mechanism.  A key idea in the paper is that if bidders optimize their bids for the dashboard, which predicts the outcome that will be obtained for any bid, then the underlying preferences of the bidders can be easily inferred from the bids.  Link to Video.

TCS Ph.D. student Yingkai Li presented a joint paper with TCS Prof. Jason Hartline and TCS Ph.D. student Yiding Feng.  The paper, “Optimal Auctions vs. Anonymous Pricing: Beyond Linear Utility“, introduces a approximation framework which approximately reduces the analysis of anonymous pricing for agents with non-linear utility to agents with linear utility in revenue-maximization. Applying this framework, constant approximation guarantee of anonymous pricing is shown for agents with public-budget utility, private-budget utility, and (a special case of) risk-averse utility.  A key idea in the paper is to define a parameterization of the regularity property that extends to agents with non-linear utility. Link to Video.

TCS Ph.D. student Chenhao Zhang had a joint paper with Nick Gravin (Shanghai University of Finance and Economics), Yaonan Jin (Columbia University) and Pinyan Lu (Shanghai University of Finance and Economics). The paper “Optimal Budget-Feasible Mechanisms for Additive Valuations” obtained tight approximation guarantee for budget-feasible mechanisms with an additive buyer. The paper proposes two-stage mechanisms that composite price-posting schemes with a pruning mechanism which greedily excludes the items with low value-per-cost ratios. A tight 2-approximation against the Knapsack and a tight 3-approximation against the Fractional-Knapsack are obtained by the proposed randomized and deterministic mechanisms respectively. Link to Video.

Symposium on Parallelism in Algorithms and Architectures(SPAA):

TCS Prof. Samir Khuller had a joint paper with visiting TCS PhD student Sheng Yang(UMD), Mosharaf Chowdhury(UMich), Manish Purohit(Google), and Jie You(UMich). The paper “Near Optimal Coflow Scheduling in Networks” focuses on the coflow scheduling problem which studies scheduling and data communication inter and intra datacenters. The main result is a randomized 2 approximation algorithm, significantly improving prior work both in theory and in practice.

Symposium on the Theory of Computing(STOC):

TCS Prof. Konstantin Makarychev had a paper with Yury Makarychev(TTIC) and Ilya Razenshteyn (Microsoft Research). This paper, “Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering“, shows that the cost of the optimal solution for Euclidean k-means or k-medians clustering is preserved up to a factor of (1+ε) under a projection onto a random O(log(k/ε)/ε2)-dimensional subspace. For k-means, this result resolves an open problem posed by Cohen, Elder, Musco, Musco, and Persu (STOC 2015); for k-medians, it answers a question raised by Kannan.

Two Northwestern papers at FOCS 2017

The Northwestern CS Theory group had two papers at the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2017), which was recently held in Berkeley, CA.

TCS Postdoc Huck Bennett had a joint paper with Alexander Golovnev (Columbia and Yahoo Research) and Noah Stephens-Davidowitz (Princeton). The paper, “On The Quantitative Hardness of CVP,” initiates the study of the fine-grained complexity of lattice problems, a study which is important to the rapidly developing field of lattice-based cryptography. As its main result, the paper shows strong hardness of the Closest Vector Problem (CVP) with certain parameters assuming the Strong Exponential Time Hypothesis (SETH).

TCS Prof. Aravindan Vijayaraghavan had a joint paper with Oded Regev
(NYU). The paper, “Learning Mixtures of Well-Separated Gaussians,”
studies the classic problem of learning a mixture of k spherical
Gaussian distributions. The paper tries to characterize the
minimum amount of separation needed between the components to
estimate the parameters (means) of the Gaussians, and presents lower
bounds and upper bounds towards this end.

 

 

Konstantin Makarychev joins Northwestern CS Theory Group!

makarychev-konstantinThe Computer Science Division at Northwestern University welcomes new faculty member Dr. Konstantin (Kostya) Makarychev as an Associate Professor, beginning immediately. Dr. Makarychev’s position is one of the ten new faculty lines in CS which were announced in June 2016.

Dr. Makarychev is a theoretical computer scientist working on approximation algorithms, beyond worst-case analysis, applications of high-dimension geometry to computer science, and combinatorial optimization for designing efficient algorithms for computationally hard problems.

Dr. Makarychev joins Northwestern from Microsoft Research in Redmond, WA (2012-2016) and IBM Research Labs in Yorktown Heights, NY (2007-2012). Further details of his background can be found on his personal webpage.

Please click here for details, and the announcement on Northwestern homepage.

“Teaching” Postdocs

The EECS Department has announced multiple postdoctoral fellowships in Computer Science.  These fellowships come with a mix of teaching and research responsibilities and a ideal for candidates who wish to strengthen both their teaching and research experience before going on the academic job market.  Successful candidates will teach one course per term and conduct independent research, collaborating as is most effective, with current Northwestern faculty and students.

One of the priority areas for these positions is algorithms.  The teaching component of this position would be the undergraduate algorithms or discrete math courses and an advanced elective in the fellow’s research area.

Postdoc Openings

The Northwestern Theory group seeks applications for 1-2 postdoctoral positions starting in September 2017. Applicants should be recent Ph.D.’s with interest in theoretical computer science. Research areas include but are not limited to algorithms, computational complexity, theoretical machine learning and optimization.  The postdoc will also be able to take advantage of the strong theory presence in the Chicago area overall. 
Applications will be accepted until the position is filled. However, applications need to be submitted by Jan 1st, 2017 to receive full consideration. Please see  http://theory.eecs.northwestern.edu/prospective-postdocs/ for details.
« Older posts