I am primarily interested in algorithms, especially algorithms for geometric problems. Most of my work to date has been related to the geometry of finite subsets of L1. I am an active participant in workshops and conferences on the theory of finite metric spaces, and I have started to become interested in Banach space theory and the theory of coarse embedding. I am also interested in algorithms for geographical information systems, cooperative games, and network construction algorithms.
I also teach and do research in the social and ethical implications of computing and information technology. In addition to general topics, I participate in research on teaching and learning in virtual worlds.
Theory 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. In submission.
- 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
- Journal version in preparation
- 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.
Ethics, Education, and Virtual Worlds
- 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. In preparation.
- 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