| Theoretical Computer Science |
|
| Faculty of Mathematics and Computer Science | |
| Jagiellonian University |
| Algorithmics Research Group |
|
Pawel M. Idziakprofessor
|
| research interests |
| algorithms |
| cryptography |
| logic |
| finite model theory |
| computational complexity |
| algebra |
| selected publications |
Fregean Varieties, International Journal of Algebra and Computation, 19(2009), 595–645. |
Definable principal congruences and solvability, Annals of Pure and Applied Logic, 157(2009), 30-49. |
Varieties with few subalgebras of powers, Transactions of the AMS, to appear |
The structure of locally finite varieties with polynomially many models, Journal of the AMS, 22(2009), 119-165. |
Tractability and learnabilty arising from algebras with few subpowers, Proc. 22 IEEE Symposium on Logic in Computer Science, 2007, pp. 213-222. |
Generative Complexity in Algebra, Memoirs of the American Mathematical Society, 175(2005), no.828. |
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. |
Polynomial interpolation in extended groups, Journal of Algebra, 271(2004), 65-107 |
Number of Malcev clones on small sets, Discrete Mathematics, 268(2003), 59-80 |
Varieties with polynomially many models, I, Fundamenta Mathematicae, 170(2001), 53-68 |
A property of the solvable radical in finitely decidable varieties, Fundamenta Mathematicae, 170(2001), 69--86 |
Natural dualities for quasivarieties generated by a finite commutative ring, Algebra Universalis, 46(2001), 285-320 |
Polynomially rich algebras, Journal of Pure and Applied Algebra, 156(2001), 33-68 |
Dualizability and graph algebras, Discrete Math., 214(2000), 145-172 |
Counting finite algebras in the Post varieties, International Journal of Algebra and Computation, 10(2000), 323-337 |
Clones with Malcev operations, International Journal of Algebra and Computation, 9(1999), 213-226 |
Decidability and structure, Logic, Algebra, Computer Science, Banach Center Publications, vol.46 (1999), 125-135 |
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 |
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 |
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. |
A characterization of finitely decidable congruence modular varieties, Transactions of the American Mathematical Society, 349(1997), 903-934 |
Definability of principal congruences in equivalential algebras, Colloquium Mathematicum, 74(1997), 225-238 |
A directly representable variety has a discrete first-order law, International Journal of Algebra and Computation, 6(1996), 269-276 |
The isomorphism problem for varieties generated by a two element algebra, Algebra Universalis, 34(1995), 430-439 |
Elementary theory of finite equivalential algebras, Reports on Mathematical Logic, 25(1991), 81--89 |
Sheaaves in universal algebra and model theory, Part II, Reports on Mathematical Logic, 24(1990), 61--86 |
Sheaves in universal algebra and model theory, Part I, Reports on Mathematical Logic, 23(1989), 39--65 |
Elementary theory of free Heyting algebras, Reports on Mathematical Logic, 23(1989), 71--73 |
Varieties with decidable finite algebras II: Permutability, Algebra Universalis, 26(1989), 247--256 |
Varieties with decidable finite algebras I: Linearity, Algebra Universalis, 26(1989), 234--246 |
Decision problem for finite algebras from arithmetical varieties with equationally definable principal congruences, Algebra Universalis, 26(1989), 33--47 |
Reduced sub-powers and the decision problem for finite algebras from arithmetical varieties, Algebra Universalis, 25(1988), 365--383 |
Undecidability of relatively free Hilbert algebras, Algebra Universalis, 25(1988), 17--26 |
Decision problem for relatively free Brouwerian semilattices, Reports on Mathematical Logic, 22(1988), 39--50 |
Decidability problem for finite Heyting algebras, Journal of Symbolic Logic, 53(1988), 729--735 |
Undecidability of pseudo-complemented semilattices, Publications of the Research Institute for Mathematical Sciences, Kyoto University, 23(1987), 559--564 |
Undecidability of free pseudo-complemented distributive lattices, Reports on Mathematical Logic, 21(1987), 97--100 |
Generalized complex algebras and regular identities, Bulletin of the Section of Logic Pol. Acad. Sci., 14(1985), 84--90. |
Filters and congruence relations in BCK-semilattices, Mathematica Japonica, 29(1984), 975--980 |
Some theorems about BCK-semilattices, Mathematica Japonica, 29(1984), 919--921 |
Lattice operations in BCK-algebras, Mathematica Japonica, 29(1984), 839--846 |
On varieties of BCK-algebras, Mathematica Japonica, 28(1983), 157--162 |
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. |
A minimal equational base for certain varieties of BCK-algebras, Bulletin of the Section of Logic Pol. Acad. Sci., 10(1981), 152--157. |
| some recent collaborators | |
| Petar Marković | University of Novi Sad, Serbia |
| Csaba Szabó | Loránd Eötvös University, Budapest, Hungary |
| Erhard Aichinger | Johannes Kepler University, Linz, Austria |
| Joel Berman | University of Illinois at Chicago, USA |
| Ralph McKenzie | Vanderbilt University, Nashville, TN, USA |
| Matthew A. Valeriote | McMaster 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 - 2009 | Algebraic aproach to Constraint Satisfaction Problem | ||
| Ministry of Science and Higher Education | |||
| Polish-Czech Project (with Charles University Prague) | |||
| 7426/2008 | |||
| 2009 - 2010 | 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 - 2012 | On-line algorihms and combinatorial games | ||
| Ministry of Science and Higher Education | |||
| N206 4923 38 | |||
| short cv | |||
| 1980 | M.S. (mathematics) | Jagiellonian University | Krakow, Poland |
| 1984 | PhD | Jagiellonian University | Krakow, Poland |
| 1986-7 | Postdoc | Hiroshima University | Hiroshima, Japan |
| 1990 | Dr. habil. | Jagiellonian University | Krakow, Poland |
| 1991 | visiting scholar | McMaster University | Hamilton, ON, Canada |
| 1993-4 | Fulbright Senior Scholar | University of California | Berkeley, CA, USA |
| 1994 | visiting professor | Waterloo University | Waterloo, ON, Canada |
| 1996 | visiting researcher | The Fields Institute for Research in Mathematical Sciences | Toronto, ON, Canada |
| 1997 | visiting researcher | Vanderbilt University | Nashville, TN, USA |
| 1999 | visiting researcher | University of Illinois at Chicago | Chicago, IL, USA |
| 2000 | visiting researcher | Vanderbilt University | Nashville, TN, USA |
| 2001 | visiting researcher | Japan Advanced Institute of Science and Technology | Ishikawa, Japan |
| 2001 - | Professor of Mathematics and Computer Science | Jagiellonian University | Krakow, Poland |
| 2002 | visiting researcher | Vanderbilt University | Nashville, TN, USA |
| 2003 | visiting researcher | University of Illinois at Chicago | Chicago, IL, USA |
| 2004 | visiting researcher | Vanderbilt University | Nashville, TN, USA |
| 2005 | visiting researcher | Vanderbilt University | Nashville, TN, USA |
| 2006 | visiting researcher | McMaster University | Hamilton, ON, Canada |
| 2008 | visiting researcher | University of Colorado at Boulder | Boulder, CO, USA |
| 2008 | visiting researcher | Vanderbilt University | Nashville, TN, USA |
