UP

C.V. UP    arXiv    DBLP

Teaching

Journal publications

[J39] Andreas Galanis, Daniel Štefankovič, Eric Vigoda. Swendsen-Wang Algorithm on the Mean-Field Potts Model.
   Random Structures and Algorithms (RSA) 54(1): 82–147, 2019. Conference version: [C35]

[J38] Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Daniel Štefankovič. Approximation via Correlation Decay When Strong Spatial Mixing Fails.
   SIAM Journal on Computing (SICOMP) 48(2): 279–349, 2019. Conference version: [C37].

[J37] Charilaos Efthymiou, Thomas P. Hayes, Daniel Štefankovič, Eric Vigoda, Yitong Yin. Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model.
   SIAM Journal on Computing (SICOMP) 48(2): 581–643, 2019. Conference version: [C38]

[J36] Marcus Schaefer, Daniel Štefankovič. The Complexity of Tensor Rank.
   Theory of Computing Systems (TCS) 62(5):1161–1174, 2018. No conference version.

[J35] Marcus Schaefer, Daniel Štefankovič. Fixed Points, Nash Equilibria, and the Existential Theory of the Reals.
   Theory of Computing Systems (TCS) 60(2):172–193, 2017. No conference version.

[J34] Andreas Galanis, Daniel Štefankovič, Eric Vigoda. Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models.
   Combinatorics, Probability & Computing (CPC) 25(4): 500–559, 2016. No conference version.

[J33] Jin-Yi Cai, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Mark Jerrum, Daniel Štefankovič, Eric Vigoda. #BIS-hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs in the Tree Non-Uniqueness Region.
   Journal of Computer and System Sciences (JCSS) 82(5): 690–711, 2016. Conference version: [C33]

[J32] Andreas Galanis, Daniel Štefankovič, Eric Vigoda, Linji Yang. Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results.
   SIAM Journal on Computing (SICOMP) 45(6): 2004–2065, 2016. Conference version: [C32]

[J31] Andreas Galanis, Daniel Štefankovič, Eric Vigoda. Inapproximability for Antiferromagnetic Spin Systems in the Tree Nonuniqueness Region.
   Journal of the Association for Computing Machinery (JACM) 62(6):50, 2015. (Electronic appendix.) Conference version: [C31]

[J30] Ricardo Restrepo, Daniel Štefankovič, Juan Carlos Vera, Eric Vigoda, Linji Yang. Phase Transition for Glauber Dynamics for Independent Sets on Regular Trees.
   SIAM Journal on Discrete Mathematics (SIDMA) 28(2): 835–861, 2014. Conference version: [C25]

[J29] Andreas Galanis, Qi Ge, Daniel Štefankovič, Eric Vigoda, Linji Yang. Improved Inapproximability Results for Counting Independent Sets in the Hard-Core Model.
   Random Structures and Algorithms (RSA) 45(1): 78–110, 2014. Conference version: [C26]

[J28] Radoslav Fulek, Michael J. Pelsmajer, Marcus Schaefer, Daniel Štefankovič. Adjacent Crossings Do Matter.
   Journal of Graph Algorithms and Applications (JGAA) 16(3): 759–782, 2012. Conference version: [C29]

[J27] Daniel Štefankovič, Santosh Vempala, Eric Vigoda. A Deterministic Polynomial-Time Approximation Scheme for Counting Knapsack Solutions.
   SIAM Journal on Computing (SICOMP) 41(2): 356–366, 2012. Conference version: [C28]

[J26] Qi Ge, Daniel Štefankovič. A Graph Polynomial for Independent Sets of Bipartite Graphs.
   Combinatorics, Probability & Computing (CPC) 21(5): 695–714, 2012. Conference version: [C24]

[J25] Qi Ge and Daniel Štefankovič. The Complexity of Counting Eulerian Tours in 4-Regular Graphs.
   Algorithmica, 63(3): 588–601, 2012. Conference version: [C23]

[J24] Daniel Štefankovič, Eric Vigoda. Fast Convergence of MCMC Algorithms for Phylogenetic Reconstruction with Homogeneous Data on Closely Related Species.
   SIAM Journal on Discrete Mathematics (SIDMA) 25(3): 1194–1211, 2011. No conference version.

[J23] Ivona Bezáková, Alistair Sinclair, Daniel Štefankovič, and Eric Vigoda. Negative Examples for Sequential Importance Sampling of Binary Contingency Tables.
   Algorithmica 64(4): 606–620, 2012. Conference version: [C12]

[J22] Michael J. Pelsmajer, Marcus Schaefer, Daniel Štefankovič. Crossing Numbers of Graphs with Rotation Systems.
   Algorithmica 60(3): 679–702, 2011. Conference version: [C16]

[J21] Marcus Schaefer, Eric Sedgwick, and Daniel Štefankovič. Spiraling and Folding: The Word View.
   Algorithmica 60(3): 609–626, 2011. Conference version: [C13]

[J20] Michael Pelsmajer, Marcus Schaefer, Daniel Štefankovič. Removing Independently Even Crossings.
   SIAM Journal on Discrete Mathematics (SIDMA) 24(2):379–393, 2010. Conference version: [C22]

[J19] Daniel Štefankovič, Santosh Vempala, Eric Vigoda. Adaptive Simulated Annealing: A Near-Optimal Connection between Sampling and Counting.
   Journal of the Association for Computing Machinery (JACM) 56(3), 2009, (DOI 10.1145/1516512.1516520). Conference version: [C18]

[J18] Michael Pelsmajer, Marcus Schaefer, Daniel Štefankovič. Removing Even Crossings on Surfaces.
   European Journal of Combinatorics (EJC), 30:1704–1717, 2009. Conference version: [C14]

[J17] Ivona Bezáková, Daniel Štefankovič, Vijay Vazirani, Eric Vigoda. Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems.
   SIAM Journal on Computing (SICOMP) 37(5):1429–1454, 2008. Conference version: [C11]

[J16] Michael Pelsmajer, Marcus Schaefer, Daniel Štefankovič. Odd Crossing Number and Crossing Number are Not the Same.
   Discrete and Computational Geometry (DCG) 39(1-3):442–454, 2008. Conference version: [C10]

[J15] Michael Pelsmajer, Marcus Schaefer, Daniel Štefankovič. Removing Even Crossings.
   Journal of Combinatorial Theory B (JCTB) 97(4):489–500, 2007. Conference version: [C9]

[J14] Manu Chhabra, Robert Jacobs, Daniel Štefankovič. Behavioral Shaping for Geometric Concepts.
   Journal of Machine Learning Research (JMLR) 8:1835–1865, 2007.

[J13] Peter Hui, Michael J. Pelsmajer, Marcus Schaefer, Daniel Štefankovič. Train Tracks and Confluent Drawings.
   Algorithmica 47(4):465-479, 2007. Conference version: [C8]

[J12] Daniel Štefankovič, Eric Vigoda. Phylogeny of Mixture Models: Robustness of Maximum Likelihood and Non-Identifiable Distributions.
   Journal of Computational Biology 14(2):156–189, 2007. No conference version.

[J11] Daniel Štefankovič, Eric Vigoda. Pitfalls of Heterogeneous Processes for Phylogenetic Reconstruction.
   Systematic Biology 56(1):113–124, 2007. No conference version.

[J10] Bruno Codenotti, Daniel Štefankovič. On the Computational Complexity of Nash Equilibria for (0,1)-Bimatrix Games.
   Information Processing Letters (IPL) 94(3):145–150, 2005. No conference version.

[J9] Marcus Schaefer, Daniel Štefankovič. Solvability of Graph Inequalities.
   SIAM Journal on Discrete Mathematics (SIDMA) 19:728–743, 2005. No conference version.

[J8] László Babai, Amir Shpilka, Daniel Štefankovič. Locally Testable Cyclic Codes.
   IEEE Transactions on Information Theory 51(8):2849–2858, 2005. Conference version: [C6]

[J7] Marcus Schaefer, Daniel Štefankovič. Decidability of String Graphs.
   Journal of Computer and System Sciences (JCSS) 68(2):319–334, 2004. Conference version: [C3]

[J6] Marcus Schaefer, Eric Sedgwick, Daniel Štefankovič. Recognizing String Graphs in NP.
   Journal of Computer and System Sciences (JCSS) 67(2):365–380, 2003. Conference version: [C5]

[J5] Rastislav Kráľovič, Branislav Rovan, Peter Ružička, Daniel Štefankovič. Efficient Deadlock-Free Multidimensional Interval Routing in Hypercube-like Networks.
   Computing and Informatics 21(3):265–287, 2002. No conference version.

[J4] László Babai, P\'eter Frankl, Samuel Kutin, Daniel Štefankovič. Set Systems with Restricted Intersections Modulo Prime Powers.
   Journal of Combinatorial Theory A (JCTA) 95(1):39–73, 2001. No conference version.

[J3] Daniel Štefankovič. Acyclic Orientations do not Lead to Optimal Deadlock-Free Packet Routing Algorithms.
   Information Processing Letters (IPL) 73(5-6):221–225, 2000. No conference version.

[J2] Peter Ružička, Daniel Štefankovič. On the Complexity of Multidimensional Routing Schemes.
   Theoretical Computer Science (TCS) 254(2):255–280, 2000. No conference version.

[J1] Rastislav Kráľovič, Peter Ružička, Daniel Štefankovič. The Complexity of Shortest Path and Dilation Bounded Interval Routing.
   Theoretical Computer Science (TCS) 234(1-2):85–107, 2000. Conference version: [C1]

Conference publications

[C48] Charilaos Efthymiou, Andreas Galanis, Thomas P. Hayes, Daniel Štefankovič, Eric Vigoda. Improved Strong Spatial Mixing for Colorings on Trees.
   23rd International Workshop on Randomization and Computation (RANDOM 2019), 48:1–16, 2019.

[C47] Ivona Bezáková, Antonio Blanca, Zongchen Chen, Daniel Štefankovič, Eric Vigoda. Lower Bounds for Testing Graphical Models: Colorings and Antiferromagnetic Ising Models.
   32nd Annual Conference on Learning Theory (COLT 2019), pp. 283–298, 2019.

[C46] Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, Daniel Štefankovič. The Complexity of Approximating the Matching Polynomial in the Complex Plane.
   46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), 22:1–22:13, 2019.

[C45] Antonio Blanca, Zongchen Chen, Daniel Štefankovič, Eric Vigoda. Structure Learning of H-colorings.
   29th International Conference on Algorithmic Learning Theory (ALT 2018), pp. 152–185, 2018.

[C44] Antonio Blanca, Andreas Galanis, Leslie Ann Goldberg, Daniel Štefankovič, Eric Vigoda, Kuan Yang. Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs.
   22nd International Workshop on Randomization and Computation (RANDOM 2018), 33:1–33:15, 2018.

[C43] Daniel Štefankovič, Eric Vigoda, John Wilmes. On Counting Perfect Matchings in General Graphs.
   13th Latin American Theoretical Informatics Symposium (LATIN 2018), pp. 873–885, 2018.

[C42] Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, Daniel Štefankovič. Inapproximability of the Independent Set Polynomial in the Complex Plane.
   50th Annual ACM Symposium on Theory of Computing (STOC 2018), pp. 1234–1240, 2018.

[C41] Charilaos Efthymiou, Thomas P. Hayes, Daniel Štefankovič, Eric Vigoda. Sampling Random Colorings of Sparse Random Graphs.
   29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), pp. 1759–1771, 2018.

[C40] Rupam Acharyya, Daniel Štefankovič. Glauber Dynamics for Ising Model on Convergent Dense Graph Sequences.
   21st International Workshop on Randomization and Computation (RANDOM 2017), 23:1–22, 2017.

[C39] Andreas Galanis, Leslie Ann Goldberg, Daniel Štefankovič. Inapproximability of the Independent Set Polynomial Below the Shearer Threshold.
   44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), 28:1–13, 2017.

[C38] Charilaos Efthymiou, Thomas P. Hayes, Daniel Štefankovič, Eric Vigoda, Yitong Yin. Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model.
   57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016): pp. 704–713, 2016. Journal version: [J37]

[C37] Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Daniel Štefankovič. Approximation via Correlation Decay When Strong Spatial Mixing Fails.
   The 43rd International Colloquium on Automata, Languages and Programming (ICALP 2016): 45:1–13, 2016. Journal version: [J38]

[C36] Marcus Schaefer and Daniel Štefankovič. The Degenerate Crossing Number and Higher-Genus Embeddings.
   23st International Symposium on Graph Drawing (GD 2015), pp. 63–74, 2015.

[C35] Andreas Galanis, Daniel Štefankovič, Eric Vigoda. Swendsen-Wang Algorithm on the Mean-Field Potts Model.
   19th International Workshop on Randomization and Computation (RANDOM 2015), pp. 815–828, 2015. Journal version: [J39]

[C34] Alistair Sinclair, Piyush Srivastava, Daniel Štefankovič, Yitong Yin. Spatial Mixing and the Connective Constant: Optimal Bounds.
   26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), pp. 1549–1563, 2015.

[C33] Jin-Yi Cai, Andreas Galanis, Leslie Goldberg, Heng Guo, Mark Jerrum, Daniel Štefankovič, Eric Vigoda. #BIS-Hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs in the Tree Non-Uniqueness Region.
   18th International Workshop on Randomization and Computation (RANDOM 2014), pp. 582–595, 2014. Journal version: [J33]

[C32] Andreas Galanis, Daniel Štefankovič, Eric Vigoda, Linji Yang. Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results.
   18th International Workshop on Randomization and Computation (RANDOM 2014), pp. 677–691, 2014. Journal version: [J32]

[C31] Andreas Galanis, Daniel Štefankovič, Eric Vigoda. Inapproximability for Antiferromagnetic Spin Systems in the Tree Non-Uniqueness Region.
   46th Annual ACM Symposium on Theory of Computing (STOC 2014), pp. 823–831, 2014. Journal version: [J31]

[C30] Marcus Schaefer and Daniel Štefankovič. Block Additivity of Z2-Embeddings.
   21st International Symposium on Graph Drawing (GD 2013), pp. 185–195, 2013.

[C29] Radoslav Fulek, Michael J. Pelsmajer, Marcus Schaefer, and Daniel Štefankovič. Adjacent Crossings Do Matter.
   19th International Symposium on Graph Drawing (GD 2011), Lecture Notes in Computer Science 7034, pp. 343–354, 2011. Journal version: [J28]

[C28] Parikshit Gopalan, Adam Klivans, Raghu Meka, Daniel Štefankovič, Santosh Vempala, and Eric Vigoda. An FPTAS for \#Knapsack and Related Counting Problems.
   52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2011), pp. 817–826, 2011. Journal version: [J27]

[C27] Radoslav Fulek, Michael J. Pelsmajer, Marcus Schaefer, and Daniel Štefankovič. Hanani-Tutte and Monotone Drawings.
   37th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2011), pp. 283–294, 2011.

[C26] Andreas Galanis, Qi Ge, Daniel Štefankovič, Eric Vigoda, and Linji Yang. Improved Inapproximability Results for Counting Independent Sets in the Hard-Core Model.
   15th International Workshop on Randomization and Computation (RANDOM 2011), pp. 567–578, 2011. Journal version: [J29]

[C25] Ricardo Restrepo, Daniel Štefankovič, Juan Carlos Vera, Eric Vigoda, and Linji Yang. Phase Transition for Glauber Dynamics for Independent Sets on Regular Trees.
   22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2011), pp. 945–956, 2011. Journal version: [J30]

[C24] Qi Ge and Daniel Štefankovič. A Graph Polynomial for Independent Sets of Bipartite Graphs.
   30th International Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010), pp. 240–250, 2010. Journal version: [J26]

[C23] Qi Ge and Daniel Štefankovič. The Complexity of Counting Eulerian Tours in 4-Regular Graphs.
   9th Latin American Theoretical Informatics Symposium (LATIN 2010), pp. 638–649, 2010. Journal version: [J25]

[C22] Michael J. Pelsmajer, Marcus Schaefer, and Daniel Štefankovič. Removing Independently Even Crossings.
   17th International Symposium on Graph Drawing (GD 2009), Lecture Notes in Computer Science Volume 5849, pp. 201–206, 2009. Journal version: [J20]

[C21] Satyaki Mahalanabis and Daniel Štefankovič. Approximating L1-Distances Between Mixture Distributions Using Random Projections.
   6th Workshop on Analytic Algorithmics and Combinatorics (ANALCO 2009), pp. 75–84, 2009.

[C20] Satyaki Mahalanabis and Daniel Štefankovič. Density Estimation in Linear Time.
   21st Annual Conference on Learning Theory (COLT 2008), pp. 503–512, 2008.

[C19] Marcus Schaefer, Eric Sedgwick, and Daniel Štefankovič. Computing Dehn Twists and Geometric Intersection Numbers in Polynomial Time.
   20th Canadian Conference in Computational Geometry (CCCG 2008), pp. 111–114, 2008.

[C18] Daniel Štefankovič, Santosh Vempala, and Eric Vigoda. Adaptive Simulated Annealing: A Near-Optimal Connection Between Sampling and Counting.
   48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), pp. 183–193, 2007. Journal version: [J19]

[C17] Marcus Schaefer, Eric Sedgwick, and Daniel Štefankovič. Spiralling and Folding: The Topological View.
   19th Canadian Conference on Computational Geometry (CCCG 2007), pp. 73–76, 2007.

[C16] Michael J. Pelsmajer, Marcus Schaefer, and Daniel Štefankovič. Crossing Number of Graphs with Rotation Systems.
   15th International Symposium on Graph Drawing (GD 2007), Lecture Notes in Computer Science 4875, pp. 3–12, 2007. Journal version: [J22]

[C15] Michael Pelsmajer, Marcus Schaefer, and Daniel Štefankovič. Crossing Numbers and Parameterized Complexity.
   15th International Symposium on Graph Drawing (GD 2007), Lecture Notes in Computer Science 4875, pp. 31–36, 2007.

[C14] Michael Pelsmajer, Marcus Schaefer, and Daniel Štefankovič. Removing Even Crossings on Surfaces.
   European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB 2007), Electronic Notes in Discrete Mathematics 29:85–90, 2007. Journal version: [J18]

[C13] Marcus Schaefer, Eric Sedgwick, and Daniel Štefankovič. Folding and Spiralling: The Word View.
   European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB 2007), Electronic Notes in Discrete Mathematics 29:101–105, 2007. Journal version: [J21]

[C12] Ivona Bezáková, Alistair Sinclair, Daniel Štefankovič, and Eric Vigoda. Negative Examples for Sequential Importance Sampling of Binary Contingency Tables.
   14th Annual European Symposium on Algorithms (ESA 2006), pp. 136–147, 2006. Journal version: [J23]

[C11] Ivona Bezáková, Daniel Štefankovič, Vijay Vazirani, and Eric Vigoda. Approximating the Permanent in O(n7) Time.
   17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), pp. 900–907, 2006. Journal version: [J17]

[C10] Michael Pelsmajer, Marcus Schaefer, and Daniel Štefankovič. Odd Crossing Number is Not Crossing Number.
   13th International Symposium on Graph Drawing (GD 2005), Lecture Notes in Computer Science 3843, pp. 386–396, 2005. Journal version: [J16]

[C9] Michael Pelsmajer, Marcus Schaefer, and Daniel Štefankovič. Removing Even Crossings.
   European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB 2005), Discrete Mathematics and Theoretical Computer Science Proceedings, pp. 105–110, 2005. Journal version: [J15]

[C8] Peter Hui, Marcus Schaefer, and Daniel Štefankovič. Train Tracks and Confluent Drawings.
   12th International Symposium on Graph Drawing (GD 2004), Lecture Notes in Computer Science 3383, pp. 318–328, 2004. Journal version: [J13]

[C7] László Babai and Daniel Štefankovič. Simultaneous Diophantine Approximation with Excluded Primes.
   15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004), pp. 1123–1129, 2004.

[C6] László Babai, Amir Shpilka, and Daniel Štefankovič. Locally Testable Cyclic Codes.
   44th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2003), pp. 116–125, 2003. Journal version: [J8]

[C5] Marcus Schaefer, Eric Sedgwick, and Daniel Štefankovič. Recognizing String Graphs in NP.
   34th Annual ACM Symposium on Theory of Computing (STOC 2002), pp. 1–6, 2002. Journal version: [J6]

[C4] Marcus Schaefer, Eric Sedgwick, and Daniel Štefankovič. Algorithms for Normal Curves and Surfaces.
   Computing and Combinatorics: 8th Annual International Conference (COCOON 2002), pp. 370–380, 2002.

[C3] Marcus Schaefer and Daniel Štefankovič. Decidability of String Graphs.
   33rd Annual ACM Symposium on Theory of Computing (STOC 2001), pp. 241–246, 2001. Journal version: [J7]

[C2] Rastislav Královič, Branislav Rovan, Peter Ružička, and Daniel Štefankovič. Efficient Deadlock-Free Multi-Dimensional Interval Routing in Interconnection Networks.
   Distributed Computing, 12th International Symposium (DISC 1998), Lecture Notes in Computer Science 1499, pp. 273–287, 1998.

[C1] Rastislav Kráľovič, Peter Ružička, and Daniel Štefankovič. The Complexity of Shortest Path and Dilation Bounded Interval Routing.
   3rd International Euro-Par Conference on Parallel Processing (EURO-PAR 1997), Lecture Notes in Computer Science 1300, pp. 258–265, 1997. Journal version: [J1]