Marc Khoury
khoury at eecs dot berkeley dot edu

I am a PhD student in Computer Science at UC Berkeley, where I work on robust machine learning and computational geometry. I am a member of the Theory Group advised by Jonathan Shewchuk.

Prior to UC Berkeley, I received a Masters in Mathematics from the University of Cambridge, where I was funded by a Churchill Scholarship. I received a Bachelors in Computer Science and Engineering from The Ohio State University, where my research was supervised by Rephael Wenger. I have also spent time at the Intel Visual Computing Lab, Microsoft Research, and AT&T Labs. I am funded by an NSF Graduate Research Fellowship.

CV  /  Google Scholar  /  GitHub  /  Twitter  /  Blog

News
  • We have released the code and data for "Learning Compact Geometric Features".
  • Our paper "Learning Compact Geometric Features" was accepted at ICCV 2017.
  • Our paper "Supporting Ruled Polygons" was accepted at CCCG 2017.
  • I gave a talk on Restricted Constrained Delaunay Triangulations at the Simons Center for Geometry and Physics.
Research

My research is focused on developing both a theoretical foundation for understanding robustness in deep learning and learning algorithms that produce decision boundaries which are resistant to adversarial attacks. In the past I have worked on computational geometry, geometric computer vision, and visualization.

Publications
srp

On the Geometry of Adversarial Examples
Marc Khoury, Dylan Hadfield-Menell
CoRR abs/1811.00525, 2018
arxiv

Adversarial examples are a pervasive phenomenon of machine learning models where seemingly imperceptible perturbations to the input lead to misclassifications for otherwise statistically accurate models. We propose a geometric framework, drawing on tools from the manifold reconstruction literature, to analyze the high-dimensional geometry of adversarial examples. In particular, we highlight the importance of codimension: for low-dimensional data manifolds embedded in high-dimensional space there are many directions off the manifold in which to construct adversarial examples. Adversarial examples are a natural consequence of learning a decision boundary that classifies the low-dimensional data manifold well, but classifies points near the manifold incorrectly. Using our geometric framework we prove (1) a tradeoff between robustness under different norms, (2) that adversarial training in balls around the data is sample inefficient, and (3) sufficient sampling conditions under which nearest neighbor classifiers and ball-based adversarial training are robust.

srp

Learning Compact Geometric Features
Marc Khoury, Qian-Yi Zhou , Vladlen Koltun
International Conference on Computer Vision (ICCV), 2017
paper / supplement / code / data

We present an approach to learning features that represent the local geometry around a point in an unstructured point cloud. Such features play a central role in geometric registration, which supports diverse applications in robotics and 3D vision. Current state-of-the-art local features for unstructured point clouds have been manually crafted and none combines the desirable properties of precision, compactness, and robustness. We show that features with these properties can be learned from data, by optimizing deep networks that map high-dimensional histograms into low-dimensional Euclidean spaces. The presented approach yields a family of features, parameterized by dimension, that are both more compact and more accurate than existing descriptors.

srp

Supporting Ruled Polygons
Nicholas J. Cavanna, Marc Khoury, Donald R. Sheehy
Canadian Conference on Computational Geometry (CCCG), 2017
arXiv

We explore several problems related to ruled polygons. Given a ruling of a polygon P, we consider the Reeb graph of P induced by the ruling. We define the Reeb complexity of P, which roughly equates to the minimum number of points necessary to support P. We give asymptotically tight bounds on the Reeb complexity that are also tight up to a small additive constant. When restricted to the set of parallel rulings, we show that the Reeb complexity can be computed in polynomial time.

rcdt

Restricted Constrained Delaunay Triangulations
Marc Khoury, Jonathan Shewchuk
In Submission

We introduce the restricted constrained Delaunay triangulation (restricted CDT). The restricted CDT generalizes the restricted Delaunay triangulation, allowing us to define a triangulation of a surface that includes a set of constraining segments. We prove sampling conditions for which the restricted CDT contains every constrained segment and is homeomorphic to the underlying surface.

fixedpt

Fixed Points of the Restricted Delaunay Triangulation Operator
Marc Khoury, Jonathan Shewchuk
Symposium on Computational Geometry (SoCG), 2016

We prove that the restricted Delaunay triangulation, thought of as an operator that takes as input a surface and a point set, iteratively applied to an input surface eventually reaches a fixed point. That is, after a finite number of iterations, the restricted Delaunay triangulation outputs a triangulation of the surface that is identical to the triangualtion on the previous iteration. Using this observation we develop new algorithms for surface reconstruction in arbitrary dimensions with unusually modest sampling requirements.

Drawing Large Graphs by Low-Rank Stress Majorization
Marc Khoury, Yifan Hu, Shankar Krishnan, Carlos Scheidegger
Computer Graphics Forum
Proceedings of Eurographics Conference on Visualization (EuroVis), 2012
paper / code

We propose a novel algorithm for computing layouts of large graphs. Our algorithm approximates the full stress majorization model by computing a low-rank approximation to the weighted Laplacian matrix. This enables our algorithm to scale to graphs with as many as several hundred thousand nodes, well beyond the limits of standard stress majorization layout algorithms.

boxdim

On the Fractal Dimension of Isosurfaces
Marc Khoury, Rephael Wenger
IEEE Transactions on Visualization and Computer Graphics (TVCG)
Proceedings of Visualization (Vis), 2010
paper

We analyze the growth rate of isosurfaces using fractal geometry. We define the isosurface fractal dimension and show that it provides a useful tool for selecting isovalues. We also show that the isosurface fractal dimension is highly correlated with topological noise in the dataset.

Posters



fixedpt





Exploring Flow Fields Using Fractal Analysis of Field Lines

Abon Chaudhuri, Teng-Yok Lee, Han-Wei Shen, Marc Khoury, Rephael Wenger
IEEE Scientific Visualization Conference (SciVis), 2012
Best Poster Award
summary

Magazine



fixedpt





On Computable Functions

Marc Khoury
Eureka (Cambridge), issue 63, 2014

Teaching
teach

CS189: Introduction to Machine Learning - Spring 2019
Head Graduate Student Instructor

CS274: Computational Geometry - Spring 2015
Co-Instructor

WeTeachScience - Spring 2014
Volunteer Mentor

Math and Statistics Learning Center - 2010-2011
Tutor


Website Template Credit