Ioannis Koutis, Publications    

• Spectrally Robust Graph Isomorphism (arxiv)
  (with Alexandra Kolla, Vivek Madan and Ali Kemal Sinop)
  ICALP 2018

• Improved Large-Scale Graph Learning through Ridge Spectral Sparsification  [pdf]
  (with Daniele Calandriello, Alessando Lazaric, Michal Valko)
  ICML 2018
  

• Directed Hamiltonicity and Out-Branchings via Generalized Laplacians (arxiv)
  (with Andreas Björklund and Petteri Kaski)
  ICALP 2017
   
• On fully dynamic graph sparsifiers (arxiv)
  (with Ittai Abraham, David Durfee, Sebastian Krinninger, Richard Peng)
   FOCS 2016
   
• Incremental Spectral Sparsification for
  Large-Scale Graph-Based Semi-Supervised Learning (arxiv)
  (with Daniele Calandriello, Alessandro Lazaric, Mihcal Valko)
  Submitted, 2016

• Algebraic fingerprints for faster algorithms [pdf]
  (with Ryan Williams)
  Communications of the ACM, January 2016
   
• Scalable Constrained Clustering: A Generalized Spectral Method [arxiv]
  with Mihai Cucuringu, Sanjay Chawla, Gary Miller, Richard Peng
  AISTATS 2016
   

• Spanning Edge Centrality: Large-scale computations and applications [pdf]
  (with Charalampos Mavroforakis, Richard Garcia-Lebron and Evimaria Terzi)
  WWW 2015

• A Generalized Cheeger Inequality [arxiv]
  (with Gary Miller, Richard Peng)

• Simple parallel and distributed algorithms for spectral graph sparsification  [arxiv]
  SPAA 2014

• A fast solver for a class of linear systems  [pdf]
  (with Gary Miller, Richard Peng)
  Communications of the ACM

• Faster spectral sparsification and numerical algorithms for SDD matrices [arxiv]
  (with Alex Levin, Richard Peng)
  This article subsumes the results of our STACS 2012 paper [pdf]

• Constrained multilinear detection for faster functional motif discovery  [arxiv]
  Information Processing Letters 2012

• Train marshalling is fixed parameter tractable [pdf]
  (with Leo Brueggeman, Michael Fellows, Rudolf Fleischer, Martin Lackner, 
          Christian Komusiewicz, Andreas Pfandler and Frances Rosamond )
  FUN2012

• A nearly-m*logn solver for SDD linear systems  [ arxiv]
  (with Gary Miller, Richard Peng)
  FOCS 2011

• Combinatorial preconditioners and multilevel solvers
  for problems in computer vision and image processing [pdf]
  (with Gary Miller, David Tolliver) 
  Computer Vision and Image Understanding 2011  (invited)
  ISVC 2009  Conference Version: [pdf] 

• Near linear-work parallel SDD solvers, 
  low-diameter decomposition and low-stretch subgraphs [pdf]
  (with Guy Blelloch, Anupam Gupta, Gary Miller, Richard Peng, Kanat Tangwongsan) 
  SPAA 2011

• Spectral counting of triangles in power-law networks
  via element-wise sparsification and triangle-based link recommendation  [pdf]
  (with Charalambos Tsourakakis, Petros Drineas, Eirinaios Michelakis, Christos Faloutsos)
  Social Network Analysis and Mining
  ASONAM 2009    Conference Version: [pdf]

• Approaching optimality for solving SDD systems [arxiv]
  (with Gary Miller, Richard Peng)
  FOCS 2010

• Hierarchical Diagonal Blocking with precision reduction applied to combinatorial multigrid [ pdf]
  (with Guy E. Blelloch, Gary Miller, Kanat Tangwongsan)
  SC10

• Limits and applications of group algebras for parameterized problems [pdf]
  (with Ryan Williams)
  The full version of the paper retracts the erroneous claim for the k-leaf problem and addresses other minor issues.
  Theoriginal paper can be found here: [pdf]
  ICALP 2009

• Faster algebraic algorithms for path and packing problems [pdf]
  ICALP 2008

• Graph partitioning into isolated, high conductance clusters:
  theory, computation and applications to preconditioning [pdf]
  (with Gary Miller)
  SPAA 2008

• Unassisted Segmentation of Multiple Retinal Layers via Spectral Rounding [pdf]
  (with David Tolliver, Hiroshi Ishikawa, Joel Shuman, Gary Miller)
  ARVO 2008

• Combinatorial and algebraic tools for optimal multilevel algorithms [pdf]
  PhD Thesis, CMU-CS-07-131

• A linear work O(n^1/6) time algorithm for solving planar Laplacians [pdf]
  (with Gary Miller)
  SODA 2007

• Parameterized complexity and improved inapproximability
  for computing the largest j-simplex in a V-polytope [pdf]
  Information Processing Letters 2006

• Dimensionality restrictions on sums over Z_p^d [pdf]
  Technical Report CMU-CS-07-103
  These results were published in a shlightly stronger form in:
  ''On the number of subsequences with given sum of sequences over finite Abelian $p$-groups'',
  by Weidong Gao and Alfred Geroldinger , Rocky Mountain J. Mathematics, 2007 [pdf]

• A faster parameterized algorithm for set packing [pdf]
  Information Processing Letters 2005

• On the hardness of approximate multivariate integration [pdf]
  APPROX 2003

• Parallel computation of matrix pseudospectra: a case for load balancing [pdf]
  (with Costas Bekas, Efstratios Gallopoulos, Efi Kokiopoulou)
  ICS 2001 
   
• Spectrum through pseudospectrum [arxiv]
  This informal publication discusses the computation of matrix eigenvalues via a descent-through-pseudospectra approach. It represents joint work with E. Gallopoulos, which was presented at FOCM 1999, and at the 5th IMACS conference on iterative methods ( abstract )

• Exclusion regions and fast estimation of pseudospectra  [pdf]
  This work was presented in an invited talk at the 2003 SIAM annual meeting