Category: CS

The Department of Computer Science will present a lecture by Tim Frick, founder and president of Mightybytes, on Friday, April 9, 2021, at 3:00 p.m.

In his talk, “People, Planet, Pixels: Toward Sustainable Digital Products and Practices,” Frick will discuss how sustainable web design and responsible digital practices can help create an internet that is clean, efficient, open, honest, regenerative, and resilient.

Speaker Bio

Tim Frick started his digital agency Mightybytes in 1998 to help purpose-driven companies, social enterprises, and large nonprofits solve problems, amplify their impact, and drive measurable results. He is the author of four books, including Designing for Sustainability: A Guide to Building Greener Digital Products and Services. Tim regularly presents at conferences and offers workshops on sustainable design, measuring impact, and problem solving in the digital economy.

Lecture Abstract

The internet has a larger environmental impact than the commercial airline industry. It currently produces approximately 3.8% of global carbon emissions, which are rising in line with our hunger to consume more data. Increasingly, web technologies are also being used to sow discontent, erode privacy, prompt unethical decisions, and, in some countries, undermine personal freedoms and the well-being of society. Web technology has the potential to bring huge benefits to society and the environment, but only if we use it wisely.

In this talk, author and digital agency owner Tim Frick will discuss how sustainable web designand responsible digital practices can help us create an internet that is clean, efficient, open, honest, regenerative, and resilient—principles outlined in the Sustainable Web Manifesto, of which Tim is a co-author. Elements of this talk are also based on Tim’s book, Designing for Sustainability: A Guide to Building Greener Digital Products and Services. Creating an internet that works for people and planet is possible. The methods described in this talk will show you how.

This lecture has been canceled.

Dr. Vijay Garg, University of Texas Austin, will present a lecture on February 19, 2021, at 3:00 p.m. The lecture is hosted by the Department of Computer Science.

Vijay Garg Bio

Vijay Garg is a Cullen Trust Endowed Professor in the Department of Electrical & Computer Engineering at The University of Texas at Austin. He received his Ph.D. in computer science at the University of California at Berkeley and B. Tech. in computer science at IIT, Kanpur.

His research interests are in distributed computing, discrete event systems and lattice theory. He is the author of “Elements of Distributed Computing” (Wiley, 2002), “Introduction to Lattice Theory with Computer Science Applications” (Wiley, 2015), and “Modeling and Control of Logical Discrete Event Systems” (Springer, 2012). He is an IEEE Fellow.

Lecture Title

Applying Predicate Detection to Discrete Optimization Problems

Lecture Abstract

We present a method to design parallel algorithms for the constrained combinatorial optimization problems. Our method solves and generalizes many classical combinatorial optimization problems including the stable marriage problem, the shortest path problem and the market clearing price problem.

These three problems are solved in the literature using Gale-Shapley algorithm, Dijkstra’s algorithm, and Demange, Gale, Sotomayor algorithm. Our method solves all these problems by casting them as searching for an element that satisfies an appropriate predicate in a distributive lattice. Moreover, it solves generalizations of all these problems — namely finding the optimal solution satisfying additional constraints called lattice-linear predicates.

For stable marriage problems, an example of such a constraint is that Peter’s regret is less than that of Paul. Our algorithm, called Lattice-Linear Predicate Detection (LLP) can be implemented in parallel with without any locks or compare-and-set instructions. It just assumes atomicity of reads and writes.

In addition to finding the optimal solution, our method is useful in enumerating all constrained stable matchings, and all constrained market clearing price vectors. The talk is an extended version of a paper that appeared in ACM SPAA’20.