Daniel Stefankovic

Theory Comput. Syst., April, 2024

Fast Sampling via Spectral Independence Beyond Bounded-degree Graphs.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, January, 2024

2023

Implementations and the independent set polynomial below the Shearer threshold.

[BibT_eX]

[DOI]

Leslie Ann Goldberg

Theor. Comput. Sci., 2023

Spectral Independence Lecture Notes.

[BibT_eX]

[DOI]

CoRR, 2023

Complexity of High-Dimensional Identity Testing with Coordinate Conditional Sampling.

[BibT_eX]

[DOI]

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

Optimal Mixing via Tensorization for Random Independent Sets on Arbitrary Trees.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2023

2022

The Degenerate Crossing Number and Higher-Genus Embeddings.

[BibT_eX]

[DOI]

Marcus Schäfer

J. Graph Algorithms Appl., 2022

Identity Testing for High-Dimensional Distributions via Entropy Tensorization.

[BibT_eX]

[DOI]

CoRR, 2022

Spiraling and Folding: The Topological View.

[BibT_eX]

[DOI]

CoRR, 2022

Sampling Colorings and Independent Sets of Random Regular Bipartite Graphs in the Non-Uniqueness Region.

[BibT_eX]

[DOI]

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

On Mixing of Markov Chains: Coupling, Spectral Independence, and Entropy Factorization.

[BibT_eX]

[DOI]

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Approximating Observables Is as Hard as Counting.

[BibT_eX]

[DOI]

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Metastability of the Potts Ferromagnet on Random Regular Graphs.

[BibT_eX]

[DOI]

Amin Coja-Oghlan

Jean Bernoulli Ravelomanana

Leslie Ann Goldberg

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

2021

The Complexity of Approximating the Matching Polynomial in the Complex Plane.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2021

Hardness of Identity Testing for Restricted Boltzmann Machines and Potts models.

[BibT_eX]

[DOI]

J. Mach. Learn. Res., 2021

Statistical mechanical analysis of neural network pruning.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence, 2021

Rapid Mixing for Colorings via Spectral Independence.

[BibT_eX]

[DOI]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

The Swendsen-Wang Dynamics on Trees.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2021

2020

Structure Learning of H-Colorings.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2020

Sampling in Uniqueness from the Potts and Random-Cluster Models on Random Regular Graphs.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2020

Inapproximability of the Independent Set Polynomial in the Complex Plane.

[BibT_eX]

[DOI]

SIAM J. Comput., 2020

Lower Bounds for Testing Graphical Models: Colorings and Antiferromagnetic Ising Models.

[BibT_eX]

[DOI]

J. Mach. Learn. Res., 2020

Understanding Diversity based Pruning of Neural Networks - Statistical Mechanical Analysis.

[BibT_eX]

[DOI]

CoRR, 2020

The Hardness of Sampling Connected Subgraphs.

[BibT_eX]

[DOI]

Andrew Read-McFarland

Proceedings of the LATIN 2020: Theoretical Informatics, 2020

The complexity of approximating averages on bounded-degree graphs.

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

Convergence of MCMC and Loopy BP in the Tree Uniqueness Region for the Hard-Core Model.

[BibT_eX]

[DOI]

SIAM J. Comput., 2019

Approximation via Correlation Decay When Strong Spatial Mixing Fails.

[BibT_eX]

[DOI]

SIAM J. Comput., 2019

Swendsen-Wang algorithm on the mean-field Potts model.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2019

Improved Strong Spatial Mixing for Colorings on Trees.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2019

2018

The Complexity of Tensor Rank.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2018

Sampling Random Colorings of Sparse Random Graphs.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

On Counting Perfect Matchings in General Graphs.

[BibT_eX]

[DOI]

John Wilmes

Proceedings of the LATIN 2018: Theoretical Informatics, 2018

2017

Fixed Points, Nash Equilibria, and the Existential Theory of the Reals.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2017

On The Projection Operator to A Three-view Cardinality Constrained Set.

[BibT_eX]

[DOI]

Proceedings of the 34th International Conference on Machine Learning, 2017

Inapproximability of the Independent Set Polynomial Below the Shearer Threshold.

[BibT_eX]

[DOI]

Leslie Ann Goldberg

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Glauber Dynamics for Ising Model on Convergent Dense Graph Sequences.

[BibT_eX]

[DOI]

Rupam Acharyya

Proceedings of the Approximation, 2017

Rapid Mixing Swendsen-Wang Sampler for Stochastic Partitioned Attractive Models.

[BibT_eX]

[DOI]

Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, 2017

2016

Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results.

[BibT_eX]

[DOI]

SIAM J. Comput., 2016

#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2016

Inapproximability of the Partition Function for the Antiferromagnetic Ising and Hard-Core Models.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2016

2015

Inapproximability for Antiferromagnetic Spin Systems in the Tree Nonuniqueness Region.

[BibT_eX]

[DOI]

J. ACM, 2015

Spatial mixing and the connective constant: Optimal bounds.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

2014

Phase Transition for Glauber Dynamics for Independent Sets on Regular Trees.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2014

Improved inapproximability results for counting independent sets in the hard-core model.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2014

Sampling Tree Fragments from Forests.

[BibT_eX]

[DOI]

Comput. Linguistics, 2014

Inapproximability for antiferromagnetic spin systems in the tree non-uniqueness region.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing, 2014

2013

BIS-Hardness for Ferromagnetic Potts in the Ordered Phase and Related Results.

[BibT_eX]

[DOI]

CoRR, 2013

Reasoning Under the Principle of Maximum Entropy for Modal Logics K45, KD45, and S5.

[BibT_eX]

[DOI]

Tivadar Papai

Henry A. Kautz

Proceedings of the 14th Conference on Theoretical Aspects of Rationality and Knowledge (TARK 2013), 2013

Block Additivity of ℤ2-Embeddings.

[BibT_eX]

[DOI]

Proceedings of the Graph Drawing - 21st International Symposium, 2013

2012

A Deterministic Polynomial-Time Approximation Scheme for Counting Knapsack Solutions.

[BibT_eX]

[DOI]

Santosh S. Vempala

SIAM J. Comput., 2012

Adjacent Crossings Do Matter.

[BibT_eX]

[DOI]

J. Graph Algorithms Appl., 2012

A Graph Polynomial for Independent Sets of Bipartite Graphs.

[BibT_eX]

[DOI]

Qi Ge

Comb. Probab. Comput., 2012

Subset Selection for Gaussian Markov Random Fields

[BibT_eX]

[DOI]

Satyaki Mahalanabis

CoRR, 2012

The Complexity of Counting Eulerian Tours in 4-regular Graphs.

[BibT_eX]

[DOI]

Qi Ge

Algorithmica, 2012

Negative Examples for Sequential Importance Sampling of Binary Contingency Tables.

[BibT_eX]

[DOI]

Algorithmica, 2012

Slice Normalized Dynamic Markov Logic Networks.

[BibT_eX]

[DOI]

Tivadar Papai

Henry A. Kautz

Proceedings of the 2nd International Workshop on Statistical Relational AI (StaRAI-12), 2012

Modeling the Locality in Graph Traversals.

[BibT_eX]

[DOI]

Proceedings of the 41st International Conference on Parallel Processing, 2012

2011

Fast Convergence of Markov Chain Monte Carlo Algorithms for Phylogenetic Reconstruction with Homogeneous Data on Closely Related Species.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2011

Spiraling and Folding: The Word View.

[BibT_eX]

[DOI]

Algorithmica, 2011

Crossing Numbers of Graphs with Rotation Systems.

[BibT_eX]

[DOI]

Algorithmica, 2011

Hanani-Tutte and Monotone Drawings.

[BibT_eX]

[DOI]

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2011

An FPTAS for #Knapsack and Related Counting Problems.

[BibT_eX]

[DOI]

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

2010

Removing Independently Even Crossings.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2010

Fast Convergence of MCMC Algorithms for Phylogenetic Reconstruction with Homogeneous Data on Closely Related Species

[BibT_eX]

[DOI]

CoRR, 2010

2009

Adaptive simulated annealing: A near-optimal connection between sampling and counting.

[BibT_eX]

[DOI]

Santosh S. Vempala

J. ACM, 2009

Approximating L1-distances Between Mixture Distributions Using Random Projections.

[BibT_eX]

[DOI]

Satyaki Mahalanabis

Proceedings of the Sixth Workshop on Analytic Algorithmics and Combinatorics, 2009

2008

Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems.

[BibT_eX]

[DOI]

SIAM J. Comput., 2008

Odd Crossing Number and Crossing Number Are Not the Same.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2008

Density Estimation in Linear Time.

[BibT_eX]

[DOI]

Satyaki Mahalanabis

Proceedings of the 21st Annual Conference on Learning Theory, 2008

Computing Dehn Twists and Geometric Intersection Numbers in Polynomial Time.

[BibT_eX]

Proceedings of the 20th Annual Canadian Conference on Computational Geometry, 2008

2007

Behavioral Shaping for Geometric Concepts.

[BibT_eX]

[DOI]

Manu Chhabra

Robert A. Jacobs

J. Mach. Learn. Res., 2007

Removing even crossings.

[BibT_eX]

[DOI]

J. Comb. Theory, Ser. B, 2007

Phylogeny of Mixture Models: Robustness of Maximum Likelihood and Non-Identifiable Distributions.

[BibT_eX]

[DOI]

J. Comput. Biol., 2007

Folding and Spiralling: The Word View.

[BibT_eX]

[DOI]

Electron. Notes Discret. Math., 2007

Removing Even Crossings on Surfaces.

[BibT_eX]

[DOI]

Electron. Notes Discret. Math., 2007

Train Tracks and Confluent Drawings.

[BibT_eX]

[DOI]

Algorithmica, 2007

Worst-Case Synchronous Grammar Rules.

[BibT_eX]

[DOI]

Daniel Gildea

Proceedings of the Human Language Technology Conference of the North American Chapter of the Association of Computational Linguistics, 2007

Crossing Numbers and Parameterized Complexity.

[BibT_eX]

[DOI]

Proceedings of the Graph Drawing, 15th International Symposium, 2007

Crossing Number of Graphs with Rotation Systems.

[BibT_eX]

[DOI]

Proceedings of the Graph Drawing, 15th International Symposium, 2007

Spiralling and Folding: The Topological View.

[BibT_eX]

[DOI]

Proceedings of the 19th Annual Canadian Conference on Computational Geometry, 2007

2005

Locally testable cyclic codes.

[BibT_eX]

[DOI]

László Babai

Amir Shpilka

IEEE Trans. Inf. Theory, 2005

Solvability of Graph Inequalities.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2005

On the computational complexity of Nash equilibria for (0, 1) bimatrix games.

[BibT_eX]

[DOI]

Bruno Codenotti

Inf. Process. Lett., 2005

Odd Crossing Number Is Not Crossing Number.

[BibT_eX]

[DOI]

Proceedings of the Graph Drawing, 13th International Symposium, 2005

2004

Decidability of string graphs.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2004

Simultaneous diophantine approximation with excluded primes.

[BibT_eX]

[DOI]

László Babai

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Train Tracks and Confluent Drawings.

[BibT_eX]

[DOI]

Peter Hui

Proceedings of the Graph Drawing, 12th International Symposium, 2004

2003

Recognizing string graphs in NP.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2003

2002

Algorithms for Normal Curves and Surfaces.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, 8th Annual International Conference, 2002

2001

Set Systems with Restricted Intersections modulo Prime Powers.

[BibT_eX]

[DOI]

J. Comb. Theory, Ser. A, 2001

2000

On the complexity of multi-dimensional interval routing schemes.

[BibT_eX]

[DOI]

Peter Ruzicka

Theor. Comput. Sci., 2000

The complexity of shortest path and dilation bounded interval routing.

[BibT_eX]

[DOI]

Rastislav Kralovic

Peter Ruzicka

Theor. Comput. Sci., 2000

Acyclic orientations do not lead to optimal deadlock-free packet routing algorithms.

[BibT_eX]

[DOI]