Theoretical Computer Science flagPL flagEN
Faculty of Mathematics and Computer Science
Jagiellonian University
 
    informatyka analityczna  
UJ coat of arms
Algorithmics Research Group abacus
 
 

Pawel M. Idziak

professor

phone: (+48-12) 664 66 48
fax: (+48-12) 664 66 72
email: email
office: ul. Łojasiewicza 6, 30-348 Kraków
room: 3064
office hours: Monday 10:00 - 10:30
Tuesday 10:00 - 10:30
Wednesday 10:00 - 10:30
Friday 10:00 - 10:30
 
 
photo

research interests
algorithms
cryptography
logic
finite model theory
computational complexity
algebra

selected publications
  • Katarzyna Grygiel, Paweł M. Idziak and Marek Zaionc,
    How big is BCI fragment of BCK logic,
    Journal of Logic and Computation 23(2013), 673--691.
  • Paweł M. Idziak, Katarzyna Słomczyńska and Andrzej Wroński,
    The commutator in equivalential algebras and Fregean varieties,
    Algebra Universalis, 65(2011), 331--340
  • Joel Berman, Paweł M. Idziak, Petar Marković, Ralph McKenzie, Matthew A. Valeriote and Ross Willard,
    Varieties with few subalgebras of powers,
    Transactions of the AMS, 362(2010), 1445--1473
  • Paweł M. Idziak, Petar Marković, Ralph McKenzie, Matthew A. Valeriote and Ross Willard,
    Tractability and learnabilty arising from algebras with few subpowers,
    SIAM Journal of Computing, 39(2010), 3023-3037
  • Paweł M. Idziak, Katarzyna Słomczyńska and Andrzej Wroński,
    Fregean Varieties,
    International Journal of Algebra and Computation, 19(2009), 595–645.
  • Paweł M. Idziak, Keith A. Kearnes, Emil W. Kiss and Matthew A. Valeriote,
    Definable principal congruences and solvability,
    Annals of Pure and Applied Logic, 157(2009), 30-49.
  • Paweł M. Idziak, Ralph McKenzie and Matthew A. Valeriote,
    The structure of locally finite varieties with polynomially many models,
    Journal of the AMS, 22(2009), 119-165.
  • Paweł M. Idziak, Petar Marković, Ralph McKenzie, Matthew A. Valeriote and Ross Willard,
    Tractability and learnabilty arising from algebras with few subpowers,
    Proc. 22 IEEE Symposium on Logic in Computer Science, 2007, pp. 213-222.
  • Joel Berman and Paweł M. Idziak,
    Generative Complexity in Algebra,
    Memoirs of the American Mathematical Society, 175(2005), no.828.
  • Paweł M.Idziak,
    Classification in finite model theory: counting finite algebras,
    Proceedings of the NATO Advanced Study Institute on Structural Theory of Automata, Semigroups, and Universal Algebra, NATO Science Series II: Mathematics, Physics and Chemistry, vol.207(2005), 149-158.
  • Erhard Aichinger and Paweł M. Idziak,
    Polynomial interpolation in extended groups,
    Journal of Algebra, 271(2004), 65-107
  • Andrei Bulatov and Paweł M. Idziak,
    Number of Malcev clones on small sets,
    Discrete Mathematics, 268(2003), 59-80
  • Paweł M. Idziak and Ralph McKenzie,
    Varieties with polynomially many models, I,
    Fundamenta Mathematicae, 170(2001), 53-68
  • Paweł M. Idziak and Matthew A.Valeriote,
    A property of the solvable radical in finitely decidable varieties,
    Fundamenta Mathematicae, 170(2001), 69--86
  • David M. Clark, Paweł M. Idziak, Lousidini Sabourin, Csaba Szabó and Ross Willard,
    Natural dualities for quasivarieties generated by a finite commutative ring,
    Algebra Universalis, 46(2001), 285-320
  • Paweł M. Idziak and Katarzyna Slomczyńska,
    Polynomially rich algebras,
    Journal of Pure and Applied Algebra, 156(2001), 33-68
  • Brian A. Davey, Pawel M. Idziak, William A. Lampe and George F. McNulty,
    Dualizability and graph algebras,
    Discrete Math., 214(2000), 145-172
  • Joel Berman and Pawel M. Idziak,
    Counting finite algebras in the Post varieties,
    International Journal of Algebra and Computation, 10(2000), 323-337
  • Pawel M. Idziak,
    Clones with Malcev operations,
    International Journal of Algebra and Computation, 9(1999), 213-226
  • Pawel M. Idziak,
    Decidability and structure,
    Logic, Algebra, Computer Science, Banach Center Publications, vol.46 (1999), 125-135
  • Pawel M. Idziak,
    Duality via sheaves,
    in: J.V. de Carvalho and I.Ferreirim, eds., Dualities, Interpretability and Ordered Structures, Centro de Algebra, Lisbon, 1999, pp.9-20
  • Pawel M. Idziak and Jerzy Tyszkiewicz,
    Monadic second order probabilities in algebra.
    Directly representable varieties and groups,
    in: Logic and Random Structures, R.B.Boppana, J.F.Lynch, (eds),
    DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Amer. Math. Soc., 33 (1997), 79-107
  • Pawel M. Idziak, Katarzyna Slomczynska and Andrzej Wronski,
    Equivalential algebras: A study of Fregean Varieties,
    manuscript 1997, 98pp.
    abstract can be found in: Proc. Workshop on Abstract Algebraic Logic,
    CRM Barcelona, Spain, July 1-5, 1997, pp.95-100.
  • Paweł M. Idziak,
    A characterization of finitely decidable congruence modular varieties,
    Transactions of the American Mathematical Society, 349(1997), 903-934
  • Pawel M. Idziak and Andrzej Wronski,
    Definability of principal congruences in equivalential algebras,
    Colloquium Mathematicum, 74(1997), 225-238
  • Stanley Burris and Pawel M. Idziak,
    A directly representable variety has a discrete first-order law,
    International Journal of Algebra and Computation, 6(1996), 269-276
  • Tomasz Gorazd and Pawel M. Idziak,
    The isomorphism problem for varieties generated by a two element algebra,
    Algebra Universalis, 34(1995), 430-439
  • Pawel M. Idziak,
    Elementary theory of finite equivalential algebras,
    Reports on Mathematical Logic, 25(1991), 81--89
  • Pawel M. Idziak,
    Sheaaves in universal algebra and model theory, Part II,
    Reports on Mathematical Logic, 24(1990), 61--86
  • Pawel M. Idziak,
    Sheaves in universal algebra and model theory, Part I,
    Reports on Mathematical Logic, 23(1989), 39--65
  • Pawel M. Idziak,
    Elementary theory of free Heyting algebras,
    Reports on Mathematical Logic, 23(1989), 71--73
  • Pawel M. Idziak,
    Varieties with decidable finite algebras II: Permutability,
    Algebra Universalis, 26(1989), 247--256
  • Pawel M. Idziak,
    Varieties with decidable finite algebras I: Linearity,
    Algebra Universalis, 26(1989), 234--246
  • Pawel M. Idziak,
    Decision problem for finite algebras from arithmetical varieties with equationally definable principal congruences,
    Algebra Universalis, 26(1989), 33--47
  • Pawel M. Idziak,
    Reduced sub-powers and the decision problem for finite algebras from arithmetical varieties,
    Algebra Universalis, 25(1988), 365--383
  • Pawel M. Idziak,
    Undecidability of relatively free Hilbert algebras,
    Algebra Universalis, 25(1988), 17--26
  • Pawel M. Idziak,
    Decision problem for relatively free Brouwerian semilattices,
    Reports on Mathematical Logic, 22(1988), 39--50
  • Paweł M. Idziak,
    Decidability problem for finite Heyting algebras,
    Journal of Symbolic Logic, 53(1988), 729--735
  • Paweł M. Idziak,
    Undecidability of pseudo-complemented semilattices,
    Publications of the Research Institute for Mathematical Sciences, Kyoto University, 23(1987), 559--564
  • Paweł M. Idziak,
    Undecidability of free pseudo-complemented distributive lattices,
    Reports on Mathematical Logic, 21(1987), 97--100
  • Paweł M. Idziak,
    Generalized complex algebras and regular identities,
    Bulletin of the Section of Logic Pol. Acad. Sci., 14(1985), 84--90.
  • Paweł M. Idziak,
    Filters and congruence relations in BCK-semilattices,
    Mathematica Japonica, 29(1984), 975--980
  • Paweł M. Idziak,
    Some theorems about BCK-semilattices,
    Mathematica Japonica, 29(1984), 919--921
  • Paweł M. Idziak,
    Lattice operations in BCK-algebras,
    Mathematica Japonica, 29(1984), 839--846
  • Paweł M. Idziak,
    On varieties of BCK-algebras,
    Mathematica Japonica, 28(1983), 157--162
  • Paweł M. Idziak,
    A finite base for the consequence operation determined by the ring Zp in the language without constants,
    Bulletin of the Section of Logic Pol. Acad. Sci., 12(1983), 76--82.
  • Paweł M. Idziak,
    A minimal equational base for certain varieties of BCK-algebras,
    Bulletin of the Section of Logic Pol. Acad. Sci., 10(1981), 152--157.
  • Paweł M. Idziak, Katarzyna Słomczyńska and Andrzej Wroński,
    The commutator in equivalential algebras and Fregean varieties,
    Algebra Universalis, 65(2011), 331--340

  • some recent collaborators 
    Petar Marković University of Novi Sad, Serbia
    Csaba Szabó Loránd Eötvös University, Budapest, Hungary
    Erhard AichingerJohannes Kepler University, Linz, Austria
    Joel BermanUniversity of Illinois at Chicago, USA
    Ralph McKenzieVanderbilt University, Nashville, TN, USA
    Matthew A. ValerioteMcMaster University, Hamilton, Ontario, Canada

    grants
    1993 - 1994 Stucture of finite algebras in decidable varieties
      Ministry of Science and Higher Education
      2 P301 029 04
    1995 - 1998 Stucture of finite algebras
      Ministry of Science and Higher Education
      P03A 031 09
    1997 - 1999 Equivalential logics and Fregean varieties
      Ministry of Science and Higher Education
      1 H01A 001 12
    2001 - 2003 Object complexity amd asymptotic density
      Ministry of Science and Higher Education
      7 T11C 022 21
    2001 - 2003 Algebraic generative complexity
      Ministry of Science and Higher Education
      5 P03A 040 21
    2005 - 2006 On-line graph coloring as a game on a bounded board
      Ministry of Science and Higher Education
      1 P03A 045 29
    2007 - 2008 On-line Coloring of Intervals, Interval Orders and Interval Graphs
      Ministry of Science and Higher Education
      N206 2728 33
    2007 - 2008 On-line Chain Partitioning Approach to Scheduling
      Ministry of Science and Higher Education
      N206 2729 33
    2007 - 2010 Gauss elimination in constraint satisfaction problems
      Ministry of Science and Higher Education
      N206 2106 33
    2008 - 2008 Research on large scale mailing system
      Ministry of Science and Higher Education, Interia.pl S.A.
    2008 - 2009 Algebraic aproach to Constraint Satisfaction Problem
      Ministry of Science and Higher Education
      Polish-Czech Project (with Charles University Prague)
      7426/2008
    2009 - 0 Optimal graph orientation problems
      Ministry of Science and Higher Education
      N206 3577 36
    2010 - 2011 On-line clique covering of interval graphs
      Ministry of Science and Higher Education
      N 206 4901 38
    2010 - 2011 On-line clique covering of interval graphs
      Ministry of Science and Higher Education
      N 206 4901 38
    2010 - 2012 On-line algorithms and combinatorial games
      Ministry of Science and Higher Education
      N206 4923 38
    2010 - 2012 Movement tracking in monitored zones
      Ministry of Science and Higher Education
      R00 0081 11
    2011 - 2014 DATALOG in Constraints Satisfaction Problem
      Polish National Science Center
      2011/01/B/ST6/01006
    2014 - 2017 Kolonoskopia -Innowacyjna diagnostyka
      NCBiR

    short cv
    1980M.S. (mathematics)Jagiellonian UniversityKrakow, Poland
    1984PhDJagiellonian UniversityKrakow, Poland
    1986-7PostdocHiroshima UniversityHiroshima, Japan
    1990Dr. habil.Jagiellonian UniversityKrakow, Poland
    1991visiting scholarMcMaster UniversityHamilton, ON, Canada
    1993-4Fulbright Senior ScholarUniversity of CaliforniaBerkeley, CA, USA
    1994visiting professorWaterloo UniversityWaterloo, ON, Canada
    1996visiting researcherThe Fields Institute for Research in Mathematical SciencesToronto, ON, Canada
    1997visiting researcherVanderbilt UniversityNashville, TN, USA
    1999visiting researcherUniversity of Illinois at ChicagoChicago, IL, USA
    2000visiting researcherVanderbilt UniversityNashville, TN, USA
    2001visiting researcherJapan Advanced Institute of Science and TechnologyIshikawa, Japan
    2001 -Professor of Mathematics
    and Computer Science
    Jagiellonian UniversityKrakow, Poland
    2002visiting researcherVanderbilt UniversityNashville, TN, USA
    2003visiting researcherUniversity of Illinois at ChicagoChicago, IL, USA
    2004visiting researcherVanderbilt UniversityNashville, TN, USA
    2005visiting researcherVanderbilt UniversityNashville, TN, USA
    2006visiting researcherMcMaster UniversityHamilton, ON, Canada
    2008visiting researcherUniversity of Colorado at BoulderBoulder, CO, USA
    2008visiting researcherVanderbilt UniversityNashville, TN, USA
     
     
      webmaster: email = a@b, a=www-tcs, b=tcs.uj.edu.pl