Leslie Ann Goldberg

Xusheng Zhang

Proceedings of the 52nd International Colloquium on Automata, Languages, and Programming, 2025

Low-Temperature Sampling on Sparse Random Graphs.

[BibT_eX]

[DOI]

Paulina Smolarova

Proceedings of the 52nd International Colloquium on Automata, Languages, and Programming, 2025

2024

Parameterised approximation of the fixation probability of the dominant mutation in the multi-type Moran process.

[BibT_eX]

[DOI]

Tassilo Constantin Schwarz

Theor. Comput. Sci., 2024

Fast Sampling of Satisfying Assignments from Random $\boldsymbol{k}$-SAT with Applications to Connectivity.

[BibT_eX]

[DOI]

Nitya Mani

Ankur Moitra

SIAM J. Discret. Math., 2024

Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity.

[BibT_eX]

[DOI]

Proc. ACM Manag. Data, 2024

The Weisfeiler-Leman Dimension of Conjunctive Queries.

[BibT_eX]

[DOI]

Proc. ACM Manag. Data, 2024

Planting and MCMC Sampling from the Potts model.

[BibT_eX]

[DOI]

Paulina Smolarova

CoRR, 2024

Two-State Spin Systems with Negative Interactions.

[BibT_eX]

[DOI]

Yumou Fei

Pinyan Lu

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

2023

Implementations and the independent set polynomial below the Shearer threshold.

[BibT_eX]

[DOI]

Daniel Stefankovic

Theor. Comput. Sci., 2023

The Weisfeiler-Leman Dimension of Existential Conjunctive Queries.

[BibT_eX]

[DOI]

CoRR, 2023

Instability of backoff protocols with arbitrary arrival rates.

[BibT_eX]

[DOI]

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

Graph Ranking and the Cost of Sybil Defense.

[BibT_eX]

[DOI]

Gwendolyn Farach-Colton

Proceedings of the 24th ACM Conference on Economics and Computation, 2023

Counting Subgraphs in Somewhere Dense Graphs.

[BibT_eX]

[DOI]

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Parameterised and Fine-Grained Subgraph Counting, Modulo 2.

[BibT_eX]

[DOI]

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Sampling from the Random Cluster Model on Random Regular Graphs at All Temperatures via Glauber Dynamics.

[BibT_eX]

[DOI]

Paulina Smolarova

Proceedings of the Approximation, 2023

2022

The Complexity of Approximating the Complex-Valued Ising Model on Bounded Degree Graphs.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., September, 2022

Fast sampling of satisfying assignments from random k-SAT.

[BibT_eX]

[DOI]

Heng Guo

CoRR, 2022

Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations.

[BibT_eX]

[DOI]

Proceedings of the PODS '22: International Conference on Management of Data, Philadelphia, PA, USA, June 12, 2022

Some New (And Old) Results on Contention Resolution (Invited Talk).

[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

Daniel Stefankovic

Eric Vigoda

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

Fast Sampling via Spectral Independence Beyond Bounded-Degree Graphs.

[BibT_eX]

[DOI]

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

2021

Faster exponential-time algorithms for approximately counting independent sets.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2021

The Complexity of Approximately Counting Retractions to Square-free Graphs.

[BibT_eX]

[DOI]

Jacob Focke

Stanislav Zivný

ACM Trans. Algorithms, 2021

Counting Homomorphisms to K4-Minor-Free Graphs, Modulo 2.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2021

Counting Homomorphisms to K4-minor-free Graphs, modulo 2.

[BibT_eX]

[DOI]

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

Approximately Counting Graph Homomorphisms and Retractions (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2021

Fast Mixing via Polymers for Random Graphs with Unbounded Degree.

[BibT_eX]

[DOI]

James Stewart

Proceedings of the Approximation, 2021

2020

Random Walks on Small World Networks.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2020

Holant Clones and the Approximability of Conservative Holant Problems.

[BibT_eX]

[DOI]

Miriam Backens

ACM Trans. Algorithms, 2020

Phase transitions of the Moran process and algorithmic consequences.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2020

Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2020

Fast Algorithms for General Spin Systems on Bipartite Expanders.

[BibT_eX]

[DOI]

James Stewart

Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science, 2020

The Complexity of Approximating the Complex-Valued Potts Model.

[BibT_eX]

[DOI]

Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science, 2020

Counting Solutions to Random CNF Formulas.

[BibT_eX]

[DOI]

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

2019

Approximating Pairwise Correlations in the Ising Model.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2019

Asymptotically optimal amplifiers for the Moran process.

[BibT_eX]

[DOI]

Konstantinos Panagiotou

Pascal Pfister

Theor. Comput. Sci., 2019

A note on the high-fugacity hard-core model on bounded-degree bipartite expander graphs.

[BibT_eX]

[DOI]

James Stewart

CoRR, 2019

Computational Complexity and Partition Functions (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science, 2019

The Complexity of Approximately Counting Retractions.

[BibT_eX]

[DOI]

Jacob Focke

Stanislav Zivný

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

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

[BibT_eX]

[DOI]

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Fast Algorithms at Low Temperatures via Markov Chains.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2019

2018

Uniqueness for the 3-State Antiferromagnetic Potts Model on the Tree.

[BibT_eX]

[DOI]

Kuan Yang

CoRR, 2018

Inapproximability of the independent set polynomial in the complex plane.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

The Complexity of Counting Surjective Homomorphisms and Compactions.

[BibT_eX]

[DOI]

Jacob Focke

Stanislav Zivný

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

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

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2018

2017

A Complexity Trichotomy for Approximately Counting List H-Colorings.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2017

Functional clones and expressibility of partition functions.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2017

Statement from EATCS President and vice Presidents about the recent US travel restrictions to foreigners.

[BibT_eX]

[DOI]

Bull. EATCS, 2017

Computational Counting (Dagstuhl Seminar 18341).

[BibT_eX]

[DOI]

Ivona Bezáková

Dagstuhl Reports, 2017

The Complexity of Approximating complex-valued Ising and Tutte partition functions.

[BibT_eX]

[DOI]

Heng Guo

Comput. Complex., 2017

A Fixed-Parameter Perspective on #BIS.

[BibT_eX]

[DOI]

Proceedings of the 12th International Symposium on Parameterized and Exact Computation, 2017

Approximating Partition Functions of Bounded-Degree Boolean Counting Constraint Satisfaction Problems.

[BibT_eX]

[DOI]

Kuan Yang

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

Inapproximability of the Independent Set Polynomial Below the Shearer Threshold.

[BibT_eX]

[DOI]

Daniel Stefankovic

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

2016

The complexity of counting locally maximal satisfying assignments of Boolean CSPs.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2016

Approximately Counting H-Colorings is $\#\mathrm{BIS}$-Hard.

[BibT_eX]

[DOI]

SIAM J. Comput., 2016

The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs.

[BibT_eX]

[DOI]

Inf. Comput., 2016

Counting 4×4 matrix partitions of graphs.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2016

A complexity trichotomy for approximately counting list H-colourings.

[BibT_eX]

[DOI]

CoRR, 2016

The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

A Complexity Trichotomy for Approximately Counting List H-Colourings.

[BibT_eX]

[DOI]

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Amplifiers for the Moran Process.

[BibT_eX]

[DOI]

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Approximation via Correlation Decay When Strong Spatial Mixing Fails.

[BibT_eX]

[DOI]

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015

A complexity classification of spin systems with an external field.

[BibT_eX]

[DOI]

Proc. Natl. Acad. Sci. USA, 2015

Approximating the partition function of planar two-state spin systems.

[BibT_eX]

[DOI]

Colin McQuillan

J. Comput. Syst. Sci., 2015

The complexity of Boolean #MaximalCSP.

[BibT_eX]

[DOI]

CoRR, 2015

Approximately Counting H-Colourings is #BIS-Hard.

[BibT_eX]

[DOI]

CoRR, 2015

Approximately Counting Locally-Optimal Structures.

[BibT_eX]

[DOI]

Rob Gysel

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Approximately Counting H-Colourings is #\mathrm BIS # BIS -Hard.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Counting Homomorphisms to Square-Free Graphs, Modulo 2.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

Evolutionary Dynamics on Graphs: Invited Talk.

[BibT_eX]

[DOI]

Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII, Aberystwyth, United Kingdom, January 17, 2015

2014

The Complexity of Approximately Counting Tree Homomorphisms.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2014

The complexity of counting homomorphisms to cactus graphs modulo 2.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2014

The Complexity of Computing the Sign of the Tutte Polynomial.

[BibT_eX]

[DOI]

SIAM J. Comput., 2014

The complexity of approximating complex-valued Ising and Tutte partition functions with applications to quantum simulation.

[BibT_eX]

[DOI]

Heng Guo

CoRR, 2014

Counting Homomorphisms to Cactus Graphs Modulo 2.

[BibT_eX]

[DOI]

Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science, 2014

Counting List Matrix Partitions of Graphs.

[BibT_eX]

[DOI]

Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

Absorption Time of the Moran Process.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2014

#BIS-Hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs in the Tree Non-uniqueness Region.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2014

2013

Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2013

The expressibility of functions on the boolean domain, with applications to counting CSPs.

[BibT_eX]

[DOI]

J. ACM, 2013

The EATCS Award 2014 - Call for nominations.

[BibT_eX]

[DOI]

Bull. EATCS, 2013

Computational Counting (Dagstuhl Seminar 13031).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2013

Approximating the Partition Function of Two-Spin Systems on Bipartite Graphs.

[BibT_eX]

[DOI]

CoRR, 2013

The complexity of approximating conservative counting CSPs.

[BibT_eX]

[DOI]

Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

2012

The complexity of approximately counting stable roommate assignments.

[BibT_eX]

[DOI]

Prasad Chebolu

Russell Martin

J. Comput. Syst. Sci., 2012

The complexity of weighted and unweighted #CSP.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2012

Can Fixation be Guaranteed in the Generalized Moran Process?

[BibT_eX]

[DOI]

CoRR, 2012

Inapproximability of the Tutte polynomial of a planar graph.

[BibT_eX]

[DOI]

Comput. Complex., 2012

Log-supermodular functions, functional clones and counting CSPs.

[BibT_eX]

[DOI]

Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 2012

Approximating fixation probabilities in the generalized Moran process.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

The Complexity of Computing the Sign of the Tutte Polynomial (and Consequent #P-hardness of Approximation).

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

2011

A Counterexample to rapid mixing of the Ge-Stefankovic Process

[BibT_eX]

[DOI]

CoRR, 2011

Stabilizing consensus with the power of two choices.

[BibT_eX]

[DOI]

Proceedings of the SPAA 2011: Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2011

A Polynomial-Time Algorithm for Estimating the Partition Function of the Ferromagnetic Ising Model on a Regular Matroid.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

2010

The mixing time of Glauber dynamics for coloring regular trees.

[BibT_eX]

[DOI]

Marek Karpinski

Random Struct. Algorithms, 2010

An approximation trichotomy for Boolean #CSP.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2010

The Complexity of Approximating Bounded-Degree Boolean #CSP (Extended Abstract)

[BibT_eX]

[DOI]

CoRR, 2010

A Complexity Dichotomy For Hypergraph Partition Functions.

[BibT_eX]

[DOI]

Comput. Complex., 2010

Brief Announcement: Stabilizing Consensus with the Power of Two Choices.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing, 24th International Symposium, 2010

The Complexity of Approximating Bounded-Degree Boolean #CSP.

[BibT_eX]

[DOI]

Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 2010

Ranking games that have competitiveness-based strategies.

[BibT_eX]

[DOI]

Proceedings of the Proceedings 11th ACM Conference on Electronic Commerce (EC-2010), 2010

Drift Analysis with Tail Bounds.

[BibT_eX]

[DOI]

Benjamin Doerr

Proceedings of the Parallel Problem Solving from Nature, 2010

Adaptive Drift Analysis.

[BibT_eX]

[DOI]

Benjamin Doerr

Proceedings of the Parallel Problem Solving from Nature, 2010

Approximating the Partition Function of the Ferromagnetic Potts Model.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

10481 Executive Summary - Computational Counting.

[BibT_eX]

[DOI]

Peter Bürgisser

Proceedings of the Computational Counting, 28.11. - 03.12.2010, 2010

10481 Abstracts Collection - Computational Counting.

[BibT_eX]

[DOI]

Peter Bürgisser

Proceedings of the Computational Counting, 28.11. - 03.12.2010, 2010

The Complexity of Approximately Counting Stable Matchings.

[BibT_eX]

[DOI]

Prasad Chebolu

Proceedings of the Approximation, 2010

2009

The complexity of weighted Boolean #CSP with mixed signs.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2009

The Complexity of Weighted Boolean #CSP.

[BibT_eX]

[DOI]

SIAM J. Comput., 2009

On the computational complexity of weighted voting games.

[BibT_eX]

[DOI]

Ann. Math. Artif. Intell., 2009

A Complexity Dichotomy for Partition Functions with Mixed Signs.

[BibT_eX]

[DOI]

Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, 2009

2008

The Mixing Time of Glauber Dynamics for Colouring Regular Trees

[BibT_eX]

[DOI]

Marek Karpinski

CoRR, 2008

A tractable and expressive class of marginal contribution nets and its applications.

[BibT_eX]

[DOI]

Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2008), 2008

On the Dimensionality of Voting Games.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence, 2008

2007

The Complexity of Ferromagnetic Ising with Local Fields.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2007

Matrix norms and rapid mixing for spin systems

[BibT_eX]

[DOI]

CoRR, 2007

Inapproximability of the Tutte polynomial.

[BibT_eX]

[DOI]

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

Frugality ratios and improved truthful mechanisms for vertex cover.

[BibT_eX]

[DOI]

Proceedings of the Proceedings 8th ACM Conference on Electronic Commerce (EC-2007), 2007

Computing good nash equilibria in graphical games.

[BibT_eX]

[DOI]

Proceedings of the Proceedings 8th ACM Conference on Electronic Commerce (EC-2007), 2007

Computational Complexity of Weighted Threshold Games.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence, 2007

2006

Improved Mixing Bounds for the Anti-Ferromagnetic Potts Model on Z2.

[BibT_eX]

[DOI]

LMS J. Comput. Math., 2006

Utilitarian resource assignment.

[BibT_eX]

[DOI]

J. Discrete Algorithms, 2006

Distributed selfish load balancing.

[BibT_eX]

[DOI]

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Nash equilibria in graphical games on trees revisited.

[BibT_eX]

[DOI]

Proceedings of the Proceedings 7th ACM Conference on Electronic Commerce (EC-2006), 2006

On Counting Homomorphisms to Directed Acyclic Graphs.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

Dobrushin Conditions and Systematic Scan.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2006

2005

Strong Spatial Mixing with Fewer Colors for Lattice Graphs.

[BibT_eX]

[DOI]

SIAM J. Comput., 2005

2004

The Complexity of Choosing an H-Coloring (Nearly) Uniformly at Random.

[BibT_eX]

[DOI]

Steven Kelk

SIAM J. Comput., 2004

A bound on the capacity of backoff and acknowledgment-based protocols.

[BibT_eX]

[DOI]

SIAM J. Comput., 2004

Random sampling of 3-colorings in Z2.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2004

trong Spatial Mixing for Lattice Graphs with Fewer Colours.

[BibT_eX]

[DOI]

Proceedings of the 45th Symposium on Foundations of Computer Science, 2004

2003

The computational complexity of two-state spin systems.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2003

A proportionate fair scheduling rule with good worst-case performance.

[BibT_eX]

[DOI]

Proceedings of the SPAA 2003: Proceedings of the Fifteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2003

2002

Convergence Of The Iterated Prisoner's Dilemma Game.

[BibT_eX]

[DOI]

Gabriel Istrate

Comb. Probab. Comput., 2002

The complexity of choosing an H-colouring (nearly) uniformly at random.

[BibT_eX]

[DOI]

Steven Kelk

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Counting and Sampling H-Colourings.

[BibT_eX]

[DOI]

Proceedings of the Randomization and Approximation Techniques, 6th International Workshop, 2002

Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows.

[BibT_eX]

[DOI]

Proceedings of the 43rd Symposium on Foundations of Computer Science, 2002

2001

An Improved Stability Bound for Binary Exponential Backoff.

[BibT_eX]

[DOI]

Hesham Al-Ammal

Theory Comput. Syst., 2001

The Natural Work-Stealing Algorithm is Stable.

[BibT_eX]

[DOI]

Petra Berenbrink

Tom Friedetzky

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

2000

An Extension of Path Coupling and Its Application to the Glauber Dynamics for Graph Colorings.

[BibT_eX]

[DOI]

Michael Mitzenmacher

SIAM J. Comput., 2000

Counting Unlabelled Subtrees of a Tree is #P-complete.

[BibT_eX]

[DOI]

LMS J. Comput. Math., 2000

Contention resolution with constant expected delay.

[BibT_eX]

[DOI]

J. ACM, 2000

Binary Exponential Backoff Is Stable for High Arrival Rates.

[BibT_eX]

[DOI]

Hesham Al-Ammal

Proceedings of the STACS 2000, 2000

An extension of path coupling and its application to the Glauber dynamics for graph colourings (extended abstract).

[BibT_eX]

[DOI]

Michael Mitzenmacher

Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

A Bound on the Capacity of Backoff and Acknowledgement-Based Protocols.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

Tight Size Bounds for Packet Headers in Narrow Meshes.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

On the relative complexity of approximate counting problems.

[BibT_eX]

[DOI]

Proceedings of the Approximation Algorithms for Combinatorial Optimization, 2000

1999

The Complexity of Gene Placement.

[BibT_eX]

[DOI]

Süleyman Cenk Sahinalp

Elizabeth Sweedyk

Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

1998

An Omega(sqrt{log log n}) Lower Bound for Routing in Optical Networks.

[BibT_eX]

[DOI]

SIAM J. Comput., 1998

The "Burnside Process" Converges Slowly.

[BibT_eX]

[DOI]

Proceedings of the Randomization and Approximation Techniques in Computer Science, 1998

Evolutionary Trees can be Learned in Polynomial Time in the Two-State General Markov Model.

[BibT_eX]

[DOI]

Mary Cryan

Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

1997

Doubly Logarithmic Communication Algorithms for Optical-Communication Parallel Computers.

[BibT_eX]

[DOI]

Frank Thomson Leighton

Satish Rao

SIAM J. Comput., 1997

Better Approximation Guarantees for Job-shop Scheduling.

[BibT_eX]

[DOI]

Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

Randomly Sampling Molecules.

[BibT_eX]

[DOI]

Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

Contention Resolution with Guaranteed Constant Expected Delay.

[BibT_eX]

[DOI]

Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

Approximation Algorithms for the Fixed-Topology Phylogenetic Number Problem.

[BibT_eX]

[DOI]

Mary Cryan

Cynthia A. Phillips

Proceedings of the Combinatorial Pattern Matching, 8th Annual Symposium, 1997

1996

Analysis of Practical Backoff Protocols for Contention Resolution with Multiple Servers.

[BibT_eX]

[DOI]

Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 1996

Constructing Computer Virus Phylogenies.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Pattern Matching, 7th Annual Symposium, 1996

Analysis of a Simple Learning Algorithm: Learning Foraging Thresholds for Lizards.

[BibT_eX]

[DOI]

Proceedings of the Ninth Annual Conference on Computational Learning Theory, 1996

1995

Minimizing Phylogenetic Number to find Good Evolutionary Trees.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Pattern Matching, 6th Annual Symposium, 1995

1994

Listing Graphs That Satisfy First-Order Sentences.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1994

An Optical Simulation of Shared Memory.

[BibT_eX]

[DOI]

Yossi Matias

Satish Rao

Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, 1994

An W(log log n) Lower Bound for Routing in Optical Networks.

[BibT_eX]

[DOI]

Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, 1994

Routing in Optical networks: The problem of contention.

[BibT_eX]

[DOI]

Proceedings of the Workshop on Interconnection Networks and Mapping and Scheduling Parallel Computations, 1994

1993

Automating Pólya Theory: The Computational Complexity of the Cycle Index Polynomial

[BibT_eX]

[DOI]

Inf. Comput., August, 1993

Polynomial space polynomial delay algorithms for listing families of graphs.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

A Doubly Logarithmic Communication Algorithm for the Completely Connected Optical Communication Parallel Computer.

[BibT_eX]

[DOI]

Frank Thomson Leighton

Satish Rao

Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, 1993

1992

Efficient Algorithms for Listing Unlabeled Graphs.

[BibT_eX]

[DOI]

J. Algorithms, 1992

1991

Efficient algorithms for listing combinatorial structures.

[BibT_eX]

[DOI]