Dr. Jan Foniok

Research Interests

Member of the group "Mathematics of OR" within IFOR

General research interests:

• the linear complementarity problem, unique-sink orientations
• constraint satisfaction, constraint programming, integration of OR and CP methods
• structural combinatorics (partial orders, homomorphisms of graphs and structures)

CV

August 2007 – December 2010

ETH Zurich, Institute for Operations Research, postdoctoral researcher

September 2004 – August 2007

Charles University in Prague, Institute of Theoretical Computer Science (ITI), junior researcher

October 2002 – July 2007

Charles University in Prague, PhD in Computer Science (Discrete Models and Algorithms), supervisor: Jaroslav Nešetřil

October 1997 – September 2002

Charles University in Prague, Master's degree in Mathematics

Publications

Journal papers

• J. Foniok, K. Fukuda, and L. Klaus. Combinatorial characterizations of K-matrices. Linear Algebra Appl., 434, pp. 68–80, 2011.
  doi:10.1016/j.laa.2010.08.008 preprint
• J. Foniok, J. Nešetřil, A. Pultr, and C. Tardif. Dualities and dual pairs in Heyting algebras. Order, 27(3), pp. 327–342, 2010.
  doi:10.1007/s11083-010-9163-3 preprint
• J. Foniok and C. Tardif. Adjoint functors and tree duality. Discrete Math. Theor. Comput. Sci., 11(2), pp. 97–110, 2009.
  paper
• J. Foniok, K. Fukuda, B. Gärtner, and H.-J. Lüthi. Pivoting in linear complementarity: Two polynomial-time cases. Discrete Comput. Geom., 42(2), pp. 187–205, 2009.
  doi:10.1007/s00454-009-9182-2 preprint
• J. Foniok, J. Nešetřil, and C. Tardif. Generalised dualities and maximal finite antichains in the homomorphism order of relational structures. European J. Combin., 29(4), pp. 881–899, 2008.
  doi:10.1016/j.ejc.2007.11.017 preprint

Refereed conference proceedings

• J. Foniok and J. Nešetřil. Splitting finite antichains in the homomorphism order. In Y. Boudabbous and N. Zaguia, editors, Proceedings of the first International Conference on Relations, Orders and Graphs: Interaction with Computer Science, pages 327–332, 2008.
  pdf
• J. Foniok, J. Nešetřil, and C. Tardif. On finite maximal antichains in the homomorphism order. Electron. Notes Discrete Math., 29, pp. 389–396, 2007.
  doi:10.1016/j.endm.2007.07.064 preprint
• J. Foniok, J. Nešetřil, and C. Tardif. Generalised dualities and finite maximal antichains. In: F. V. Fomin (ed.), Graph-Theoretic Concepts in Computer Science (Proceedings of WG 2006), vol. 4271 of Lecture Notes in Comput. Sci., pp. 27–36. Springer-Verlag, 2006.
  doi:10.1007/11917496_3 preprint
• J. Foniok. Structural aspects of the class of relational structures. In: J. Šafránková (ed.), WDS’03 Proceedings of Contributed Papers, Part I, pp. 238–242. Charles University, Matfyzpress, Prague, 2003.
  pdf

Doctoral Thesis

Homomorphisms and Structural Properties of Relational Systems

Preprints

• J. Foniok, J. Nešetřil, and C. Tardif. Interleaved adjoints on directed graphs.
  arXiv
• J. Foniok, B. Gärtner, L. Klaus, and M. Sprecher. Counting unique-sink orientations.
  arXiv

Notes and Other

• P-matrix recognition is co-NP-complete, a summary of the proof by Coxson
• The Linear Complementarity Problem: A Combinatorial Approach, a poster
• Amoebas and SDP, a project report with Daniel Johannsen

Slides for talks

• Fête of Combinatorics and Computer Science, August 2008 (Sproinks)
• Sixth Joint Operations Research Days, 11 September 2008 (USO)
• Kolloquium über Kombinatorik, 15 November 2008 (splitting antichains)
• Unique-Sink Orientations of Hypercubes and Linear Complementarity Problems, 14 September 2010

list of publications in pdf format

Diary

• From February 2011: Laboratoire d'Informatique de l'École Polytechnique (LIX), Palaiseau, France.
• July–August 2011: Mathematics of Constraint Satisfaction at the Fields Institute, Toronto, Canada.
• 11–15/7/2011: Workshop on Graph Homomorphisms, Fields Institute, Toronto, Canada.
• 19–22/7/2011: London Mathematical Society Northern Regional Meeting and Workshop on Homogeneous Structures, University of Leeds, UK.
• 2–6/8/2011: Workshop on Algebra and CSPs, Fields Institute, Toronto, Canada.
• From September 2011: Queen's University, Kingston ON, Canada.

Links

• Open Problem Garden