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.
- Book page at Amazon.com
- Follow us on Twitter @EiaCC
- Get assignments and in-class activities on ethicsinacomputingculture.com
- 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
- Amazon page for "Dating and Philosophy"
- 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.
- Human Technology
- 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.
- DOI Link to the ACM digital library
- Link to game materials, under Creative Commons license.
- 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.
- DOI Link to IEEE
- 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.
Miami University 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.
- DOI Link to ACM
- 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.
- DOI Link to ACM
- Best paper award, FOCS 2003. An extended abstract appeared in: Foundations of Computer Science, 2003 Proceedings 44th Annual IEEE Symposium on, 2003; 514-523.
- PDF: Contains the main proofs in a previously unpublished appendix, but is superceded by the JACM version.
- 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.
- My dissertation, published as Princeton tech report TR-701-04, 2004.
- 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.
- DOI Link to JoSH
- An extended abstract appeared in: Proceedings of the 13th annual ACM-SIAM Symposium on Discrete Algorithms. 2002; 535-539.
- PDF: I provide the conference version here, but it is also available from the ACM digital library.