I am interested in algorithms for geometric problems and the social and ethical implications of computing. In algorithms I am most interested in approximation algorithms and hardness results for metric space embedding problems, such as dimension reduction, and Euclidean and rectilinear embeddings of graph metrics. In computing ethics I am interested in a wide array of topics, but my current focus is on the implications of the (hypothetical) wide-spread adoption of augmented reality.

Ethics, Education, and Virtual Worlds

Ethics in a Computing Culture
With Alton Sanders. My new undergraduate textbook on computer ethics from Course Technology (a division of Cengage). To appear, February 15, 2012.
An Invitation to Computer Science
The book is by Schneider and Gersting. I have contributed some material for the "Ethics" chapter of the 6th edition.
Dating and Play in Virtual Worlds
I analyze the ontological status of dating through the lens of virtual worlds. Using Huizinga's classical work on play, "Homo Ludens," I show that dating in virtual worlds can be more real than real world dating. I also indicate a link between computer "hacking" and "The Game," as described Neil Strauss. This paper is intended for a general audience, to introduce Huizinga's ideas, as well as the idea (from Heim's "The Erotic Ontology of Cyberspace") of using virtual worlds as a philosophical lens.
In "Dating and Philosophy: Flirting with Big Ideas," from Blackwell Philosophy, January 2011
Using Rationale to Assist Student Cognitive and Intellectual Development
We report on an initial exploration of using Design Rationale in a traditional data structures course to encourage student reflection and creativity. We hypothesize that Design Rationale force students to remain longer in a liminal "undecided" state about the design problem at hand, leading to greater reflection, greater creativity, and better solutions.
With Janet Burge, in "Human Technology" 6(1), May 2010.
This work is being re-printed in the Springer HCI series in a volume edited by J. Carroll
The Heart of a Whistle-blower: A Corporate Decision-Making Game for Computer Ethics Classes
I present a game useful in teaching students about whistle-blowing. The game helps students confront a question about themselves: "How much am I REALLY willing to risk, to ensure that my company acts ethically?"
Bo Brinkman. "The Heart of a Whistle-blower: A Corporate Decision-Making Game for Computer Ethics Classes," in The Proceedings of the 40th ACM Technical Symposium on Computer Science Education (SIGCSE), pages 316-320, 2009.
Using SL and Linden Lab as case studies to problematize the creation of new technologies
This paper describes an assignment sequence that forces students to confront their own assumptions and myths about technology. Computing students cannot (responsibly) create new technologies if they are not able to forsee the consequences of new technologies ... but computing students, with their high level of comfort with technology, often assume that any changes they make will be "improvements" rather than "disruptions." I explain why, in the current moment, Second Life presents a unique opportunity for challenging a student's comfort with internet technologies. I also give many examples of key questions that can be used to induce cognitive dissonance, and help students to critically engage with questions of the impact of new technologies on social structures.
Brinkman B. Presented at SLEDcc 2008.
Privacy of Student Work
I argue that students do have a privacy right that is violated when their works are archived by plagiarism detection systems. These rights flow from the law, the rights and duties of educators, and from consequences to the student. I then propose a protocol for adopting (or not) plagiarism detection systems that respects student rights, while not completely removing the usefuless of such systems.
Brinkman B. Presented at the 2009 Annual Meeting of the Association for Practical and Professional Ethics.
Best early-career faculty paper award, APPE 2009.
Under revision for the Journal of Science and Engineering Ethics.
Enhancing Undergraduate Computer Science Education Through a University-wide Summer Research Program
In this paper we document the successes of our Undergraduate Summer Scholars program.
Brinkman B, Cross V, Opyrchal L. The Proceedings of the 37th Annual Frontiers in Education Conference (FIE). 2007; S4B-1--S4B-6.

Algorithms Publications

Degree-constrained minimum latency trees
We study the problem of constructing multicast trees in (semi-)metric spaces. Motivated by practical and experimental algorithms work, we focus on algorithms which guarantee bounded degree and low total latency. Our definition of the problem naturally interpolates between the traveling repairman problem (which is APX-Complete) and single source shortest paths (which is in P). The main result of the paper is that even when the degree constraint is fairly loose, the problem remains APX-Hard. Several other results are included: A constant factor approximation for metrics with bounded doubling dimension (but with degree depending on the doubling dimension), some experimental results, and a simple O(log n) approximation algorithm.
Brinkman B and Helmick M. Technical report.
Vertex Cuts, Random Walks, and Dimension Reduction in Series-Parallel Graphs
We consider questions about vertex cuts in graphs, random walks in metric spaces, and dimension reduction in L1 and L2 ; these topics are intimately connected because they can each be reduced to the existence of various families of real- valued Lipschitz maps on certain metric spaces. We view these issues through the lens of shortest-path metrics on series-parallel graphs, and we discuss the implications for a variety of well-known open problems.
Brinkman B, Karagiozova A, Lee JR. Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007; 621-630.
On the Impossibility of Dimension Reduction in l1.
In this paper, we showed that finite subsets of l1 can require a number of dimensions polynomial to the number of points in the set, when only constant distortion is allowed. This is in stark contrast to the result of Johnson and Lindenstrauss which shows that any subset of l2 can be represented with only a logarithmic number of dimensions, and small distortion. Our proof uses LP duality, and also the notion of stretch-limited embeddings proposed by Charikar and Sahai.
Brinkman B, Charikar M. Journal of the ACM (JACM), 2005; 52: 766-788.
Best paper award, FOCS 2003. An extended abstract appeared in: Foundations of Computer Science, 2003 Proceedings 44th Annual IEEE Symposium on, 2003; 514-523.
Metric Space Embeddings in l1: An Optimization Approach.
I describe a method for exploring l1 embeddings using linear programming. I demonstrate how this method was used to prove that dimension reduction in l1 is not possible.
A Randomized Online Algorithm for Bandwidth Utilization
In this paper we consider the problem of TCP congestion control in an adversarial setting where one user may choose to defect from the established AIMD protocol. We argue that, if one assumes some fairly weak smoothness conditions on the bandwidth availability of a network, a MIMD protocol actually achieves near optimal competitive ratio.
Arora S, Brinkman B. J of Scheduling 2004; 7: 187-194.
An extended abstract appeared in: Proceedings of the 13th annual ACM-SIAM Symposium on Discrete Algorithms. 2002; 535-539.