My Publications

Journals

• S. Ohlsson, R. H. Sloan, Gy. Turán, A. Urasky: Measuring an artificial intelligence system's performance on a Verbal IQ test for young children, J. of Experimental and Theoretical Artificial Intelligence 29 (2017), 679-693.
  
  
• R. H. Sloan, D. Stasi, Gy. Turán: Hydras: Directed hypergraphs and Horn formulas, Theoretical Computer Science 658 (2017), 417-428.
  
  
• B. Fish, Gy. Turán: Betweenness centrality profiles in trees, J. of Complex Networks (2017).
  
  
• R. H. Sloan, D. Stasi, Gy. Turán: Random Horn formulas and propagation connectivity for directed hypergraphs, Discrete Mathematics & Theoretical Computer Science 14 (2012), 29-36.
  
  
• D. I. Diochnos, R. H. Sloan, Gy. Turán: On multiple-instance learning of halfspaces, Information Processing Letters 112 (2012), 933-936.
  
  
• D. Mubayi, Gy. Turán: Finding bipartite subgraphs efficiently, Information Processing Letters 110 (2010), 174-177.
  
  
• M. Langlois, R. H. Sloan, Gy. Turán: Horn upper bounds and renaming. Journal on Satisfiability, Boolean Modeling and Computation, 7 (2010), 1-15.
  
  
• R. H. Sloan, B. Szörényi, Gy. Turán: Projective DNF formulae and their revision. Discrete Applied Mathematics 156 (2008), 530-544.
  
  
• R. H. Sloan, B. Szörényi, Gy. Turán: On k-term DNF with the largest number of prime implicants, SIAM J. on Discrete Mathematics, 21 (2008), 987-998.
  
  
• P. Berman, B. DasGupta, D. Mubayi, R. H. Sloan, Gy. Turáan, Y. Zhang: The inverse protein folding problem on 2D and 3D lattices, Discrete Applied Mathematics 155 (2007), 719-732.
  
  
• R. H. Sloan, B. Szörényi, Gy. Turan: Revising threshold functions, Theoretical Computer Science 382 (2007), 198-208. (ALT 2004 Special Issue.)
  
  
• Z. Füredi, R. H. Sloan, K. Takata, Gy. Turán: On set systems with a threshold property, Discrete Mathematics, 306 (2006), 3097-3111.
  
  
• D. Mubayi, Gy. Turán, Y. Zhao: The DNF exception problem, Theoretical Computer Science 352 (2006), 85-96.
  
  
• J. Goldsmith, R. H. Sloan and Gy. Turán: Theory revision with queries: Horn, read-once, and parity formulas, Artificial Intelligence Journal 156 (2004), 139-176.
  
  
• M. Grohe, Gy. Turán: Learnability and definability in trees and similar structures, Theory of Computing Systems 37 (2004), 193-220. (STACS 2002 Special Issue.)
  
  
• J. Goldsmith, R. H. Sloan and Gy. Turán: Theory revision with queries: DNF Formulas, Machine Learning 47 (2002), 257-295.
  
  
• T. Horváth, Gy. Turán: Learning logic programs with structured background knowledge, Artificial Intelligence Journal 128 (2001), 31-97.
  
  
• R. H. Sloan, K. Takata, Gy. Turán: On frequent sets of Boolean matrices, Annals of Mathematics and Artificial Intelligence 24 (1998), 193-209.
  
  
• D. Angluin, M. Krikis, R. H. Sloan, and Gy. Turán: Malicious omissions and errors in answers to membership queries, Machine Learning 28 (1997), 211-255.
  
  
• Gy. Turán, F. Vatan: On the computation of Boolean functions by analog circuits of bounded fan-in, Journal of Computer and System Sciences 54 (1997), 199-212.
  
  
• Gy. Turán, F. Vatan: A size-depth trade-off for the analog computation of Boolean functions, Information Processing Letters 59 (1996), 251-254.
  
  
• Gy. Turán: On the complexity of planar circuits, Computational Complexity 5 (1995), 24-42.
  
  
• W. Maass, Gy. Turán: Algorithms and lower bounds for on-line learning of geometric concepts, Machine Learning 14 (1994), 251-269.
  
  
• A. Hajnal, W. Maass, P. Pudlak, M. Szegedy, Gy. Turán: Threshold circuits with bounded depth, Journal of Computer and System Sciences 46 (1993), 129-154.
  
  
• H. D. Gröger, Gy. Turán: A linear lower bound for the size of threshold circuits, Bulletin of the European Association for Theoretical Computer Science 50 (1993), 220-222.
  
  
• W. Maass, G. Schnitger, E. Szemeredi, Gy. Turán: Two tapes versus one for off-line Turing machines, Computational Complexity 3 (1993), 392-401.
  
  
• U. Faigle, Gy. Turán: The communication complexity of interval orders, Discrete Applied Mathematics 40 (1992), 19-28.
  
  
• W. Maass, Gy. Turán: Lower bounds and separation results for on-line learning models, Machine Learning 9 (1992), 107-145.
  
  
• Gy. Turán: Lower bounds for synchronous circuits and planar circuits, Information Processing Letters 30 (1989), 37-40.
  
  
• U. Faigle, W. Kern, Gy. Turán: On the performance of on-line algorithms for partition problems, Acta Cybernetica 9 (1989), 107-119.
  
  
• S. Buss, Gy. Turán: Resolution proofs for generalized pigeonhole principles, Theoretical Computer Science 62 (1988), 311-317.
  
  
• U. Faigle, Gy. Turán: Sorting and recognition problems for ordered sets, SIAM Journal on Computing 17 (1988), 100-113.
  
  
• L. Babai, P. Hajnal, E. Szemerédi, Gy. Turán: A lower bound for one-time-only branching programs, Journal of Computer and System Sciences 35 (1987), 153-162.
  
  
• U. Faigle, Gy. Turán: The complexity of semiorders and interval orders, Discrete Mathematics 63 (1987), 131-141.
  
  
• W. Cook, C. R. Coullard, Gy. Turán: On the complexity of cutting plane proofs, Discrete Applied Mathematics 18 (1987), 25-38.
  
  
• L. Babai, Gy. Turán: The complexity of defining a relation on a finite graph, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 33 (1987), 277-288.
  
  
• U. Faigle, L. Lovasz, R. Schrader, Gy. Turán: Searching in trees, series-parallel and interval orders, SIAM Journal on Computing 15 (1986), 1075-1084.
  
  
• Gy. Turán: On the succinct representation of graphs, Discrete Applied Mathematics 8 (1984), 289-294.
  
  
• Gy. Turán: On the definability of properties of finite graphs, Discrete Mathematics 49 (1984), 291-302.
  
  
• Gy. Turán: The critical complexity of graph properties, Information Processing Letters 18 (1984), 151-153.
  
  
• Gy. Turán: On the complexity of graph grammars, Acta Cybernetica 6 (1983), 271-280.
  
  
• E. Györi, Gy. Turán: Stack of pancakes, Studia Scientia Math. Hung. 13 (1978), 133-137.
  

Conferences

• H. Naik, Gy. Turán: Explanation from specification, Explainable Agency in AI Workshop, 35th AAAI (2021)
  
  
• K. Chubarian, Gy. Turán: Interpretability of Bayesian network classifiers: OBDD approximation and polynomial threshold functions, ISAIM (2020)
  
  
• V. Balogh, G. Berend, D. Diochnos, Gy. Turán: Understanding the semantic content of sparse word embeddings using a commonsense knowledge base, AAAI (2020)
  
  
• J. Yaggie, Gy. Turán: Characterizability in Horn belief revision, JELIA (2016), 497-511.
  
  
• B. Fish, J. Kun, Á. D. Lelkes, L. Reyzin, Gy. Turán. On the computational complexity of MapReduce, DISC 2015.
  
  
• L. Michael, A. C. Kakas, R. Miller, Gy. Turán: Cognitive Programming, AIC (2015), 3-18.
  
  
• Gy. Turán, J. Yaggie: Characterizability in Belief Revision, IJCAI (2015), 3236-3242.
  
  
• F. Vafaee, Gy. Turán, P. C. Nelson, T. Y. Berger-Wolf: Balancing the exploration and exploitation in an adaptive diversity guided genetic algorithm, IEEE Congress on Evolutionary Computation (2014), 2570-2577.
  
  
• Sz. Iván, Á. D. Lelkes, J. Nagy-György, B. Szörényi, Gy. Turán: Biclique Coverings, Rectifier Networks and the Cost of e-Removal, DCFS (2014), 174-185.
  
  
• F. Vafaee, Gy. Turán, P. C. Nelson, T. Y. Berger-Wolf: Among-site rate variation: adaptation of genetic algorithm mutation rates at each single site, GECCO (2014), 863-870.
  
  
• S. Ohlsson, R. H. Sloan, Gy. Turán, A. Urasky:Verbal IQ of a Four-Year Old Achieved by an AI System. AAAI (Late-Breaking Developments) (2013)
  
  
• S. Ohlsson, R. H. Sloan, Gy. Turán, A. Urasky: Verbal IQ of a Four-Year Old Achieved by an AI System, 11th International Symposium on Logical Formalizations of Commonsense Reasoning (Commonsense 2013) (2013)
  
  
• T. Y. Berger-Wolf, D. I. Diochnos, A. London, A. Pluhár, R. H. Sloan, Gy. Turán: Commonsense knowledge bases and network analysis, 11th International Symposium on Logical Formalizations of Commonsense Reasoning (Commonsense 2013)
  
  
• S. Ohlsson, R. H. Sloan, Gy. Turán, D. Uber, A. Urasky: An Approach to Evaluate AI Commonsense Reasoning Systems. FLAIRS Conference (2012)
  
  
• D. Stasi, R. H. Sloan, Gy. Turán: Hydra formulas and directed hypergraphs: A preliminary report. ISAIM (2012)
  
  
• K. V. Adaricheva, R. H. Sloan, B. Szörényi, Gy. Turán: Horn Belief Contraction: Remainders, Envelopes and Complexity. KR 2012 (2012)
  
  
• R. H. Sloan, D. Stasi, Gy. Turán: Hydras: Directed Hypergraphs and Horn Formulas. WG 2012: 237-248 (2012)
  
  
• K. V. Adaricheva, R. H. Sloan, B. Szörényi, Gy. Turán: Horn Belief Contraction: Remainders, Envelopes and Complexity. AAAI Spring Symposium: Logical Formalizations of Commonsense Reasoning (2011)
  
  
• F. Vafaee, Gy. Turán, P. C. Nelson: Optimizing genetic operator rates using a markov chain model of genetic algorithms. GECCO 2010: 721-728 (2010)
  
  
• A. Bhattacharya, B. DasGupta, D. Mubayi, Gy. Turán: On Approximate Horn Formula Minimization. ICALP (1) 2010: 438-450
  
  
• D. I. Diochnos, Gy. Turán: On Evolvability: The Swapping Algorithm, Product Distributions, and Covariance. SAGA 2009: 74-88
  
  
• M. Langlois, R. H. Sloan, B. Szörényi, Gy. Turán: Horn Complements: Towards Horn-to-Horn Belief Revision. AAAI 2008: 466-471
  
  
• M. Langlois, D. Mubayi, R. H. Sloan, Gy. Turán: Combinatorial problems for Horn clauses. ISAIM 2008
  
  
• M. Langlois, R. H. Sloan, Gy. Turán: Horn upper bounds and renaming, Theory and Applications of Satisfiability Testing. SAT 2007, Springer LNCS 4501, 80-93, 200
  
  
• P. Hajnal, Z. Liu, Gy. Turán: Nearest neighbor representations of Boolean functions, 9th International Symposium on Artificial Intelligence and Mathematics, 2006.
  
  
• M. Langlois, R. H. Sloan, Gy. Turán: Horn upper bounds of random 3-CNF: a computational study, 9th International Symposium on Artificial Intelligence and Mathematics, 2006.
  
  
• J. Goldsmith, R. H. Sloan, B. Szörényi, and Gy. Turán: Revision algorithms using queries: results and problems, Workshop on Learning with Logic and Logics for Learning, Japanese Society for AI, 39-44, 2005.
  
  
• J. Goldsmith, R. H. Sloan, B. Szörényi, Gy. Turán: New revision algorithms, 15. Algorithmic Learning Theory (ALT 2004), Springer LNCS 3244, 395-409, 2004.
  
  
• P. Berman, B. DasGupta, D. Mubayi, R. H. Sloan, Gy. Turán, Y. Zhang: The protein sequence design problem in the canonical model on 2D and 3D lattices, 15. Combinatorial Pattern Matching Symposium (CPM 2004), Springer LNCS 3109, 244-253, 2004.
  
  
• R. H. Sloan, B. Szörényi, Gy. Turán: Projective DNF and their revision, Learning Theory and Kernel Machines (16. COLT/Kernel 2003), Springer LNCS 2777, 625-639, 2003.
  
  
• T. Horváth, R. H. Sloan, and Gy. Turán: Learning logic programs with unary partial function graph background knowledge, First International Workshop on Mining Graphs, Trees and Sequences (MGTS-03), 2003.
  
  
• M. Grohe, Gy. Turán: Learnability and definability in trees and similar structures, 19. Symposium on Theoretical Aspects of Computer Science (STACS), Springer LNCS 2285, 645-658, 2002.
  
  
• J. Goldsmith, R. H. Sloan, B. Szörényi, Gy. Turán: Improved Algorithms for Theory Revision with Queries, 13. Annual Conference on Computational Learning Theory (COLT ), 236-247, 2000.
  
  
• R. H. Sloan, Gy. Turán: On theory revision with queries, 12. Annual Conference on Computational Learning Theory (COLT ), 41-52, 1999.
  
  
• I. Tsapara, Gy. Turán: Learning atomic formulas with prescribed properties, 11. Annual Conference on Computational Learning Theory (COLT), 166-174, 1998.
  
  
• T. Horváth, R. H. Sloan, Gy. Turán: Learning logic programs with random classification noise, 6. International Workshop on Inductive Logic Programming (ILP), S. Muggleton ed., Springer LNAI 1314, 315-336, 1997.
  
  
• T. Horvath, R. H. Sloan, Gy. Turán: Learning logic programs by using the product homomorphism method, 10. Conference on Computational Learning Theory (COLT), 10-20, 1997.
  
  
• R. H. Sloan, Gy. Turán: Learning from incomplete boundary queries using split graphs and hypergraphs, Computational Learning Theory: Third European Conference (EuroCOLT '97), S. Ben-David ed. Springer LNAI 1208, 38-50, 1997.
  
  
• T. Horváth, Gy. Turán: Learning logic programs with structured background knowledge, 5. International Workshop on Inductive Logic Programming (ILP), 1995.
  
  
• W. Maass, Gy. Turán: On learnability and predicate logic, Bar-Ilan Symposium on the Foundations of Artificial Intelligence (BISFAI), 75-85, 1995.
  
  
• Gy. Turán, F. Vatan: On the computation of Boolean functions by analog circuits of bounded fan-in, 35. Foundations of Computer Science (FOCS), 553-564, 1994.
  
  
• R. H. Sloan, Gy. Turán: Learning with queries but incomplete information, 7. ACM Conference on Computational Learning Theory (COLT), 237-245, 1994.
  
  
• Gy. Turán: Lower bounds for PAC learning with queries, 6. ACM Conference on Computational Learning Theory (COLT), 1993.
  
  
• H. D. Gröger, Gy. Turán: On linear decision trees computing Boolean functions, 18. International Conference on Automata, Languages and Programming (ICALP), J. L. Albert, B. Monien, M. R. Artalejo, eds., Springer LNCS 510, 707-718, 1991.
  
  
• W. Maass, Gy. Turán: On the complexity of learning from counterexamples and membership queries, 31. Foundations of Computer Science (FOCS), 203-210, 1990.
  
  
• W. Maass, Gy. Turán: On the complexity of learning with counterexamples, 30. Foundations of Computer Science (FOCS), 262-267, 1989.
  
  
• Gy. Turán: On restricted Boolean circuits, Fundamentals of Computation Theory (FCT), J. Csirik, J. Demetrovics, F. Gecseg, eds. Springer LNCS 380, 460-469, 1989.
  
  
• A. Hajnal, W. Maass, Gy. Turán: On the communication complexity of graph properties, 20. Symposium on the Theory of Computing (STOC), 186-191, 1988.
  
  
• U. Faigle, Gy. Turán: Static on-line decomposition of series-parallel and interval orders, 13. Conference of the German Society for Operations Research (SOR), Methods of Operations Research, B. Fuchssteiner, T. Lengauer, H. J. Skala, eds. 60 (1988), 197-203.
  
  
• A. Hajnal, W. Maass, P. Pudlák, M. Szegedy, Gy. Turán: Threshold circuits with bounded depth, 28. Foundations of Computer Science (FOCS), 99-110, 1987.
  
  
• M. Ajtai, L. Babai, P. Hajnal, J. Komlós, P. Pudlák, V. Rödl, E. Szemerédi, Gy. Turán: Two lower bounds for branching programs, 17. Symposium on the Theory of Computing (STOC), 30-38, 1986.
  
  
• U. Faigle, Gy. Turán: Sorting and recognition problems for ordered sets, Symposium on the Theoretical Aspects of Computer Science (STACS), K. Mehlhorn ed., Springer LNCS 182, 109-118, 1985.
  
  
• Gy. Turán: Models of computation for graph theoretic problems, Graph Theoretic Problems in Computer Science (WG'84), U. Pape ed., 369-381, 1984.
  
  
• U. Faigle, L. Lovász, R. Schrader, Gy. Turán: Search problems in ordered sets, Operations Research, D. Ohse et al. eds., 411-415, 1984.
  
  
• Gy. Turán: On the greedy algorithm for an edge-partitioning problem, Theory of Algorithms, Colloquia of the Bolyai Mathematical Society 44, 405-423, 1984.
  
  
• Gy. Turán: Cellular graph automata and second-order definable graph properties, Fundamentals of Computer Science (FCT), F. Gecseg ed., Springer LNCS 117, 384-393, 1981.
  

Surveys, Book Chapters

• R. H. Sloan, B. Szörényi, Gy. Turán: Learning Boolean functions with queries, in: Boolean Models and Methods in Mathematics, Computer Science and Engineering, Y. Crama, P. L. Hammer ed.
  
  
• M. Langlois, D. Mubayi, R. H. Sloan, Gy. Turán: Combinatorial Problems for Horn Clauses, in: Graph Theory, Computational Intelligence and Thought, M. Lipshteyn, V. E. Levit, R. M. McConnell eds., Springer, 54-65, 2009.
  
  
• Gy. Turán: Remarks on computational learning theory, Annals of Mathematics and Artificial Intelligence 28 (2000), 43-45.
  
  
• Gy. Turán: Learning theory, in: Artificial Intelligence, I. Futo ed., 535-549. Aula, 1998. (In Hungarian.)
  
  
• Gy. Turán, F. Vatan: Linear decision lists and partitioning algorithms for the construction of neural networks, in: Foundations of Computational Mathematics: Selected Papers of a Conference held at in IMPA in Rio de Janeiro, January 1997, F. Cucker, M. Shub eds., Springer, 414-423, 1997.
  
  
• Gy. Turán: It is a long way from input to output (a survey of computational learning theory), in: Jenseits von Kunst, P. Weibel ed., 436-441. Passagen Verlag, 1997. (In German.)
  
  
• T. Horváh, Gy. Turán: Learning logic programs with structured background knowledge, in: Advances in Inductive Logic Programming, L. De Raedt ed., 172-191. IOS Press, Ohmsha, 1996.
  
  
• W. Maass, Gy. Turán: How fast can a threshold gate learn?, in: Computational Learning Theory and Natural Learning Systems: Constraints and Prospects, S. Hanson, G. Drastal, R. Rivest eds., 381-414. MIT Press, 1994.
  
  
• Gy. Turán: Computational learning theory and neural networks: a survey of selected topics, in: Theoretical Advances in Neural Computation and Learning, V. P. Roychowdhury, K. Y. Siu, A. Orlitsky eds., 243-293. Kluwer, 1994.
  
  
• Gy. Turán: A survey of some aspects of computational learning theory, in: Fundamentals of Computation Theory (FCT), L. Budach ed., Springer LNCS 529, 89-103, 1991.
  
  
• U. Faigle, Gy. Turán: Communication complexity, in: Computational Graph Theory, G. Tinhofer et al. eds., Computing Supplementum 7, 141-153. Springer, 1990.
  
  
• Gy. Turán: Notions of complexity in computer science: a survey, in: Modelling Complex Systems: Studies for the Hungarian Ministry of Industry, 1983. (In Hungarian.)
  
  
• Gy. Turán: Parallel program schemata: a survey, Hungarian Academy of Sciences Automata Theory Research Group, Technical Report, 1981. (In Hungarian.)