Dimitrios Kanoulas

And now, what's going to happen to us without barbarians?
They were, those people, a kind of solution.
[C. Cavafy, "Waiting for the Barbarians"]

Dimitrios Kanoulas
[Δημήτρης Κανούλας]

Address:
College of Computer & Information Science
Northeastern University
360 Huntington Avenue,
West Village H, #202
Boston, MA 02115, USA

Office: West Village H, #214 (0016173732502)

e-mail: echo "name@ccs.neu.edu" | sed -re 's!name!dkanou!'

I support: Free and Open Source software and hardware.
(See: GNU Project, Free Software Foundation, and Open Source Hardware).
I am a big fan of Open Source Ecology.

NEWS: in my twitter account

I am currently a Ph.D. student at the Geometric and Physical Computing (GPC) Lab in the College of Computer and Information Science at Northeastern University, advised by Prof. Marsette Vona.
I am working in the field of computer vision and robotics, and in particular, I am developing new estimation and planning algorithms for articulated robots that locomote in uncertain natural environment. I am focused on developing new theoretical results on sensing, real-time map building and self/environment modeling of curved surface contact patches which include statistical models of uncertainty, for the purpose of bipedal and humanoid locomotion on very uneven 3D terrain, using SLAM and perception systems.

I started out as a member of the Algorithms and Theory group at Northeastern University , advised by Prof. Rajmohan Rajaraman, and particularly Algorithmic aspects of Game Theory [Equilibria complexity, and applications of A.G.T. in the Networks domain], Approximation Algorithms, and Combinatorial and Linear Optimization remain some of my primary research interests.

I did my undergraduate studies in the school of Computer Engineering and Informatics at University of Patras in Greece, advised by Prof. Paul Spirakis, and Dr. Haralampos Tsaknakis.

Curriculum Vitae

I'm interested in:

Computer Vision and Robotics: Stereo & Monocular Computer Vision, Perception Systems, Probabilistic Robotics, Simultaneous Localization and Mapping (SLAM), and Machine Learning in Computer Vision (Object Recognition and Classification).
Algorithms and Complexity: Algorithmic Game Theory, Approximation Algorithms and Complexity, Combinatorial and Linear Optimization, and Design and Analysis of Algorithms.

My Erdos Number: 3 [László Lovász (1) -> Rajmohan Rajaraman (2) -> Dimitrios Kanoulas (3)]

Here is my CV: [.pdf]

Publications

[DBLP, FacetedDBLP, Google Scholar, ResearchGate, Academia, Linkedin, iamresearcher, mendeley]

"Sparse Surface Modeling with Curved Patches",
with Marsette Vona.
In the 2013 IEEE International Conference on Robotics and Automation, ICRA 2013.

Traditional segmentation algorithms for range images create partitions of connected and non-overlapping---but potentially irregularly shaped---regions corresponding to world surfaces. This paper presents an alternative paradigm based on regularly shaped curved patches (paraboloids) that model local contact regions potentially compatible with e.g. a robot's toe, heel, or fingertip. These patches randomly sample the environment surface but are not required to strictly partition it. They are fit to neighborhoods of the range data and then validated for fit quality and fidelity to the actual data---extrapolations (like hole-filling) which are not directly supported by data are avoided. Two different neighborhood formation methods based on k-d tree and triangle mesh data structures are compared, and results are presented for 10 datasets taken in natural rocky terrain.
```
@inproceedings{KV13,
author = {Dimitrios Kanoulas and Marsette Vona},
title = {Sparse Surface Modeling with Curved Patches},
BookTitle = {Proceedings of the 2013 {IEEE} International Conference on Robotics and Automation (ICRA 2013)},
pages = {},
year = {2013}
}
		
```
[abstract] [bib] [.pdf] [Acceptance Rate: 39%]
"CTY Robotics and Applied Computing",
with Marsette Vona.
Manual Documentation, December 2012
[.pdf]
"Cache me if you can: Capacitated Selfish Replication in Networks",
with Ragavendran Gopalakrishnan, Naga Naresh Karuturi, C. Pandu Rangan, Rajmohan Rajaraman, and Ravi Sundaram.
In the Latin American Symposium on Theoretical Informatics, LATIN 2012.

Motivated by peer-to-peer (P2P) networks and content delivery applications, we study Capacitated Selfish Replication (CSR) games, which involve nodes on a network making strategic choices regarding the content to replicate in their caches. Selfish replication games were introduced in [6], who analyzed the uncapacitated case leaving the capacitated version as an open direction.
In this work, we study pure Nash equilibria of CSR games with an emphasis on hierarchical net- works, which have been extensively used to model the communication costs of content delivery and P2P systems. The best result from previous work on CSR games for hierarchical networks [21, 27] is the existence of a Nash equilibrium for a (slight generalization of a) 1-level hierarchy when the utility function is based on the sum of the costs of accessing the replicated objects in the network. Our main result is an exact polynomial-time algorithm for finding a Nash Equilibrium in any hierarchical network using a new technique which we term "fictional players". We show that this technique extends to a general frame- work of natural preference orders, orders that are entirely arbitrary except for two natural constraints - "Nearer is better" and "Independence of irrelevant alternatives". This axiomatic treatment captures a vast class of utility functions and even allows for nodes to simultaneously have utility functions of completely different functional forms.
Using our axiomatic framework, we next study CSR games on arbitrary networks and delineate the boundary between intractability and effective computability in terms of the network structure, object preferences, and the total number of objects. In addition to hierarchical networks, we show the existence of equilibria for general undirected networks when either object preferences are binary or there are two objects. For general CSR games, however, we show that it is NP-hard to determine whether equilibria exist. We also show that the existence of equilibria in strongly connected networks with two objects and binary object preferences can be determined in polynomial time via a reduction to the well-studied even-cycle problem. Finally, we introduce a fractional version of CSR games (F-CSR) with application to content distribution using erasure codes. We show that while every F-CSR game instance possesses an equilibrium, finding an equilibrium in an F-CSR game is PPAD-complete.
```
@inproceedings{GKKRRS12,
author = {Gopalakrishnan, Ragavendran and Kanoulas, Dimitrios and Karuturi, Naga Naresh and Pandu Rangan, C. and Rajaraman, Rajmohan and Sundaram, Ravi},
title = {Cache me if you can: Capacitated Selfish Replication Games},
booktitle = {Proceedings of the 10th Latin American international conference on Theoretical Informatics},
series = {LATIN'12},
year = {2012},
isbn = {978-3-642-29343-6},
location = {Arequipa, Peru},
pages = {420--432},
numpages = {13},
publisher = {Springer-Verlag},
address = {Berlin, Heidelberg},
} 
		
```
[abstract] [bib] [.pdf] [arXiv] [slides] [Acceptance Rate: 36%]
"Curved Surface Contact Patches with Quantified Uncertainty",
with Marsette Vona.
In the IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2011.

We introduce a set of 10 bounded curved-surface patch types suitable for modeling local contact regions both in the environment and on a robot. We present minimal geometric parameterizations using the exponential map for spatial pose both in the usual 6DoF case and also for patches with revolute symmetry that have only 5DoF. We then give an algorithm to fit any patch type to point samples of a surface, with quantified uncertainty both in the input points (including nonuniform variance, common in data from range sensors) and in the output patch. Finally, we outline how such patches can be composed into a spatial patch map of the available contact surfaces both on and around a robot.
```
@inproceedings{VK11,
author = {Marsette Vona and Dimitrios Kanoulas},
title = {Curved Surface Contact Patches with Quantified Uncertainty},
BookTitle = {Proceedings of the 2011 {IEEE/RSJ} International Conference on Intelligent Robots and Systems (IROS)},
pages = {1439-1446},
year = {2011}
}
		
```
[abstract] [bib] [.pdf] [videos] [source code] [Acceptance Rate: 32%]
"Performance evaluation of a descent algorithm for bi-matrix games",
with Haralampos Tsaknakis, and Paul Spirakis.
In the 4th Workshop on Internet & Network Economics, WINE 2008.

In this paper we present an implementation and performance evaluation of a descent algorithm that was proposed in [1] for the computation of approximate Nash equilibria of non-cooperative bi-matrix games. This algorithm, which achieves the best polynomially computable approximate equilibria till now, is applied here to several problem instances designed so as to avoid the existence of easy solutions. Its performance is analyzed in terms of quality of approximation and speed of convergence. The results demonstrate signicantly better performance than the theoretical worst case bounds, both for the quality of approximation and for the speed of convergence. This motivates further investigation into the intrinsic characteristics of descent algorithms applied to bi-matrix games.We discuss these issues and provide some insights about possible variations and extensions of the algorithmic concept that could lead to further understanding of the complexity of computing equilibria. We also prove here a new signicantly better bound on the number of loops required for convergence of the descent algorithm.
```
@inproceedings{TSK08,
author = {Haralampos Tsaknakis and Paul G. Spirakis and Dimitrios Kanoulas},
title = {Performance Evaluation of a Descent Algorithm for Bi-matrix Games},
booktitle = {WINE},
year = {2008},
pages = {222-230},
}
		
```
[abstract] [bib] [Paper .pdf] [TR .pdf] [arXiv] [Acceptance Rate: 33%]
"Approximate Nash Equilibrium"
Conducting theoretical and experimental research on optimal algorithms
that can result in better approximate Nash Equilibria in bimatrices games.
Dimitrios Kanoulas
Bachelor`s Thesis, University of Patras, Computer Engineering and Informatics Dept.
co-advisors: Paul Spirakis and Haralampos Tsaknakis, July 2008

Over the last few years, there has been explosive growth in the research done at the interface of computer science, and game theory. Algorithmic Game Theory, that develops the idea of this intersection, plays an increasingly important role in theoretical computer science and in logic. In this research work we are trying to investigate one of the many open problems that Algorithmic Game Theory deals with. We focus on the computation of Nash Equilibrium and in particular we are investigate the computation of approximate Nash Equilibrium.
We present an implementation and performance evaluation of a descent algorithm that was proposed in [Tsaknakis, Spirakis, WINE 2008] for the computation of approximate Nash equilibria of non-cooperative bi-matrix games. This algorithm, which achieves the best polynomially computable approximate equilibria till now, is applied here to several problem instances designed so as to avoid the existence of easy solutions. Its performance is analyzed in terms of quality of approximation and speed of convergence. The results demonstrate signicantly better performance than the theoretical worst case bounds, both for the quality of approximation and for the speed of convergence. This motivates further investigation into the intrinsic characteristics of descent algorithms applied to bi-matrix games.We discuss these issues and provide some insights about possible variations and extensions of the algorithmic concept that could lead to further understanding of the complexity of computing equilibria. We also prove here a new signicantly better bound on the number of loops required for convergence of the descent algorithm.
```
@bachelorsthesis{Kanoulas08,
author = {Dimitrios Kanoulas},
title = {Approximate Nash Equilibrium},
year = {2008}
}
		
```
[abstract] [bib] [.pdf] (in Greek)

Professional Experience

Northeastern University, Boston, MA, USA
1. Teaching Assistant for the courses:
  1. CSU390 Theory of Computation (Undergraduate), Fall 2008.
  2. CSU390 Theory of Computation (Undergraduate), Spring 2009.
  3. CS4300 Computer Graphics (Undergraduate), Spring 2011.
  4. CS5010 Program Design Paradigms (Graduate), [Fall 2011, Spring 2012].
  5. CTY Project Robotics and Applied Computing Day Proram for Gifted Middles School students [December 2012].
2. Research Assistant: Summer 2009, Fall 2009, Spring 2010, Summer 2010, Fall 2010, Summer 2011, Fall 2012, Spring 2013.
INRIA, Grenoble, Rhone-Alpes, France
1. Research Intern (e-Motion group, Prof. Christian Laugier): Summer 2012
Professional Services
1. Reviewer: IROS2013, NEU Outstanding Graduate Student Awards '13, IEEE_RAM2013, ICRA2013, Humanoids2012, IROS2011, CCC2010.
2. External Reviewer: SODA2010, GLOBECOM2009.

Research Group & Seminar

Geometric and Physical Computing Seminar

Algorithmic Game Theory Reading Group

Fall 2008

Spring 2009

Boston University - Northeastern Joint Theory of Computation Seminar

Seminar on Communications, Algorithms, Networking, and Security (SCANS)

Northeastern PhdStudentSeminar

DUTH Robotics Team

Run SCANS and Ph.D. Seminar: Fall 2009, Spring 2010
Organized and run the Algorithmic Game Theory Reading Group: Fall 2008, Spring 2009