Jin-Yi Cai

Ben Young

ACM Trans. Comput. Theory, September, 2024

Counting Cycles on Planar Graphs in Subexponential Time.

[BibT_eX]

[DOI]

Ashwin Maran

Algorithmica, February, 2024

Bounded Degree Nonnegative Counting CSP.

[BibT_eX]

[DOI]

Daniel P. Szabo

ACM Trans. Comput. Theory, 2024

A Uniformly Random Solution to Algorithmic Redistricting.

[BibT_eX]

[DOI]

CoRR, 2024

2023

Bipartite 3-regular counting problems with mixed signs.

[BibT_eX]

[DOI]

Yin Liu

J. Comput. Syst. Sci., August, 2023

Complexity classification of the eight-vertex model.

[BibT_eX]

[DOI]

Inf. Comput., August, 2023

Holographic Algorithms on Domains of General Size.

[BibT_eX]

[DOI]

Theory Comput. Syst., June, 2023

A Complexity Trichotomy for k-Regular Asymmetric Spin Systems Using Number Theory.

[BibT_eX]

[DOI]

Comput. Complex., June, 2023

Dichotomy result on 3-regular bipartite non-negative functions.

[BibT_eX]

[DOI]

Theor. Comput. Sci., March, 2023

A dichotomy for bounded degree graph homomorphisms with nonnegative weights.

[BibT_eX]

[DOI]

Martin E. Dyer

J. Comput. Syst. Sci., 2023

Shor's Algorithm Does Not Factor Large Integers in the Presence of Noise.

[BibT_eX]

[DOI]

CoRR, 2023

Planar 3-way Edge Perfect Matching Leads to A Holant Dichotomy.

[BibT_eX]

[DOI]

CoRR, 2023

The Complexity of Counting Planar Graph Homomorphisms of Domain Size 3.

[BibT_eX]

[DOI]

Ashwin Maran

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Restricted Holant Dichotomy on Domains 3 and 4.

[BibT_eX]

[DOI]

Yin Liu

Proceedings of the Combinatorial Optimization and Applications, 2023

Properties of Position Matrices and Their Elections.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence, 2023

2022

Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain.

[BibT_eX]

[DOI]

SIAM J. Comput., 2022

FKT is Not Universal - A Planar Holant Dichotomy for Symmetric Constraints.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2022

Perfect matchings, rank of connection tensors and graph homomorphisms.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2022

2021

On a Theorem of Lovász that (&sdot, H) Determines the Isomorphism Type of H.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2021

The complexity of counting edge colorings for simple graphs.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2021

An FPTAS for the square lattice six-vertex and eight-vertex models at low temperatures.

[BibT_eX]

[DOI]

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

New Planar P-time Computable Six-Vertex Models and a Complete Complexity Classification.

[BibT_eX]

[DOI]

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

2020

Dichotomy for Holant∗ Problems on the Boolean Domain.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2020

Beyond #CSP: A dichotomy for counting weighted Eulerian orientations with ARS.

[BibT_eX]

[DOI]

Inf. Comput., 2020

FPRAS via MCMC where it mixes torpidly (and very little effort).

[BibT_eX]

[DOI]

CoRR, 2020

On a Theorem of Lovász that hom(⋅, H) Determines the Isomorphism Type of H.

[BibT_eX]

[DOI]

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

Counting Perfect Matchings and the Eight-Vertex Model.

[BibT_eX]

[DOI]

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

From Holant to Quantum Entanglement and Back.

[BibT_eX]

[DOI]

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

Dichotomy for Graph Homomorphisms with Complex Values on Bounded Degree Graphs.

[BibT_eX]

[DOI]

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

A Dichotomy for Real Boolean Holant Problems.

[BibT_eX]

[DOI]

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

Approximability of the Eight-Vertex Model.

[BibT_eX]

[DOI]

Proceedings of the 35th Computational Complexity Conference, 2020

2019

Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2019

On a Theorem of Lovász that hom(·, H) Determines the Isomorhphism Type of H.

[BibT_eX]

[DOI]

CoRR, 2019

Complexity of Counting Weighted Eulerian Orientations with ARS.

[BibT_eX]

[DOI]

CoRR, 2019

A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights.

[BibT_eX]

[DOI]

Comput. Complex., 2019

Approximability of the Six-vertex Model.

[BibT_eX]

[DOI]

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

2018

Clifford gates in the Holant framework.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2018

Holographic algorithms beyond matchgates.

[BibT_eX]

[DOI]

Inf. Comput., 2018

Complexity classification of the six-vertex model.

[BibT_eX]

[DOI]

Inf. Comput., 2018

Dichotomy for Real Holantc Problems.

[BibT_eX]

[DOI]

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

2017

Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP.

[BibT_eX]

[DOI]

SIAM J. Comput., 2017

Complexity of Counting CSP with Complex Weights.

[BibT_eX]

[DOI]

J. ACM, 2017

Dichotomy for Real Holantc Problems.

[BibT_eX]

[DOI]

CoRR, 2017

A Complexity Trichotomy for the Six-Vertex Model.

[BibT_eX]

[DOI]

CoRR, 2017

2016

Holographic Algorithms.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Holant Problems.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Complexity Dichotomies for Counting Graph Homomorphisms.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

A Complete Dichotomy Rises from the Capture of Vanishing Signatures.

[BibT_eX]

[DOI]

SIAM J. Comput., 2016

Nonnegative Weighted #CSP: An Effective Complexity Dichotomy.

[BibT_eX]

[DOI]

SIAM J. Comput., 2016

Holant Problems for 3-Regular Graphs with Complex Edge Functions.

[BibT_eX]

[DOI]

Theory Comput. Syst., 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

Erratum to: Signature Theory in Holographic Algorithms.

[BibT_eX]

[DOI]

Algorithmica, 2016

2015

A Holant Dichotomy: Is the FKT Algorithm Universal?

[BibT_eX]

[DOI]

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014

The complexity of complex weighted Boolean #CSP.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2014

A collapse theorem for holographic algorithms with matchgates on domain size at most 4.

[BibT_eX]

[DOI]

Inf. Comput., 2014

The Complexity of Counting Edge Colorings and a Dichotomy for Some Higher Domain Holant Problems.

[BibT_eX]

[DOI]

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013

The Minimum Consistent Subset Cover Problem: A Minimization View of Data Mining.

[BibT_eX]

[DOI]

IEEE Trans. Knowl. Data Eng., 2013

Partition functions on kk-regular graphs with {0, 1}{0, 1}-vertex assignments and real edge functions.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2013

Graph Homomorphisms with Complex Values: A Dichotomy Theorem.

[BibT_eX]

[DOI]

SIAM J. Comput., 2013

Matchgates Revisited.

[BibT_eX]

[DOI]

Aaron Gorenstein

Electron. Colloquium Comput. Complex., 2013

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

[BibT_eX]

[DOI]

CoRR, 2013

A complete dichotomy rises from the capture of vanishing signatures: extended abstract.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing Conference, 2013

Dichotomy for Holant* Problems with Domain Size 3.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Complexity Dichotomy for Counting Problems.

[BibT_eX]

[DOI]

Proceedings of the Language and Automata Theory and Applications, 2013

On optimal differentially private mechanisms for count-range queries.

[BibT_eX]

[DOI]

Proceedings of the Joint 2013 EDBT/ICDT Conferences, 2013

2012

Spin systems on k-regular graphs with complex edge functions.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2012

On differentially private frequent itemset mining.

[BibT_eX]

[DOI]

Chen Zeng

Jeffrey F. Naughton

Proc. VLDB Endow., 2012

Dichotomy for Holant* Problems with a Function on Domain Size 3

[BibT_eX]

[DOI]

CoRR, 2012

Holographic reduction, interpolation and hardness.

[BibT_eX]

[DOI]

Comput. Complex., 2012

From Holant to #CSP and Back: Dichotomy for Holant c Problems.

[BibT_eX]

[DOI]

Sangxia Huang

Algorithmica, 2012

Holographic Algorithms on Domain Size k > 2.

[BibT_eX]

[DOI]

Proceedings of the Theory and Applications of Models of Computation, 2012

Inapproximability after Uniqueness Phase Transition in Two-Spin Systems.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Optimization and Applications, 2012

2011

A computational proof of complexity of some restricted counting problems.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2011

Computational Complexity of Holant Problems.

[BibT_eX]

[DOI]

SIAM J. Comput., 2011

Foreword.

[BibT_eX]

[DOI]

Alan L. Selman

J. Comput. Syst. Sci., 2011

Holographic algorithms: From art to science.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2011

Approximation and hardness results for label cut and related problems.

[BibT_eX]

[DOI]

J. Comb. Optim., 2011

Honeynet games: a game theoretic approach to defending network monitors.

[BibT_eX]

[DOI]

J. Comb. Optim., 2011

Signature Theory in Holographic Algorithms.

[BibT_eX]

[DOI]

Algorithmica, 2011

Dichotomy for Holant* Problems of Boolean Domain.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Spin Systems on Graphs with Complex Edge Functions and Specified Degree Regularities.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics - 17th Annual International Conference, 2011

Non-negatively Weighted #CSP: An Effective Complexity Dichotomy.

[BibT_eX]

[DOI]

Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011

Progress in Complexity of Counting Problems.

[BibT_eX]

[DOI]

Proceedings of the Frontiers in Algorithmics and Algorithmic Aspects in Information and Management, 2011

2010

On blockwise symmetric signatures for matchgates.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2010

Non-negative Weighted #CSPs: An Effective Complexity Dichotomy

[BibT_eX]

[DOI]

CoRR, 2010

Quadratic Lower Bound for Permanent Vs. Determinant in any Characteristic.

[BibT_eX]

[DOI]

Dong Li

Comput. Complex., 2010

A Dichotomy for k-Regular Graphs with {0, 1}-Vertex Assignments and Real Edge Functions.

[BibT_eX]

[DOI]

Proceedings of the Theory and Applications of Models of Computation, 7th Annual Conference, 2010

Holant Problems for Regular Graphs with Complex Edge Functions.

[BibT_eX]

[DOI]

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

From Holant to #CSP and Back: Dichotomy for Holantc Problems.

[BibT_eX]

[DOI]

Sangxia Huang

Proceedings of the Algorithms and Computation - 21st International Symposium, 2010

Holographic Algorithms with Matchgates Capture Precisely Tractable Planar_#CSP.

[BibT_eX]

[DOI]

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

On Tractable Exponential Sums.

[BibT_eX]

[DOI]

Proceedings of the Frontiers in Algorithmics, 4th International Workshop, 2010

2009

Holographic algorithms: The power of dimensionality resolved.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2009

On the Theory of Matchgate Computations.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2009

Preface to Special Issue: Theory and Applications of Models of Computation (TAMC).

[BibT_eX]

[DOI]

S. Barry Cooper

Angsheng Li

Math. Struct. Comput. Sci., 2009

A Novel Information Transmission Problem and its Optimal Solution.

[BibT_eX]

[DOI]

Eric Bach

Commun. Inf. Syst., 2009

Holant problems and counting CSP.

[BibT_eX]

[DOI]

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

An Attacker-Defender Game for Honeynets.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, 15th Annual International Conference, 2009

2008

Holographic algorithms: guest column.

[BibT_eX]

[DOI]

SIGACT News, 2008

A Family of Counter Examples to an Approach to Graph Isomorphism

[BibT_eX]

[DOI]

CoRR, 2008

Basis Collapse in Holographic Algorithms.

[BibT_eX]

[DOI]

Comput. Complex., 2008

A quadratic lower bound for the permanent and determinant problem over any characteristic != 2.

[BibT_eX]

[DOI]

Dong Li

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Holographic algorithms with unsymmetric signatures.

[BibT_eX]

[DOI]

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

Holographic Algorithms by Fibonacci Gates and Holographic Reductions for Hardness.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007

Valiant's Holant Theorem and matchgate tensors.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2007

S2p is subset of ZPPNP.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2007

On Block-wise Symmetric Signatures for Matchgates.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2007

Bases Collapse in Holographic Algorithms.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2007

The minimum consistent subset cover problem and its applications in data mining.

[BibT_eX]

[DOI]

Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2007

2006

Time-Space Tradeoff in Derandomizing Probabilistic Logspace.

[BibT_eX]

[DOI]

Dieter van Melkebeek

Theory Comput. Syst., 2006

On zero error algorithms having oracle access to one query.

[BibT_eX]

[DOI]

J. Comb. Optim., 2006

On the Theory of Matchgate Computations

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

On Symmetric Signatures in Holographic Algorithms.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

Some Results on Matchgates and Holographic Algorithms.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

Random Access to Advice Strings and Collapsing Results.

[BibT_eX]

[DOI]

Algorithmica, 2006

2005

Progress in Computational Complexity Theory.

[BibT_eX]

[DOI]

Hong Zhu

J. Comput. Sci. Technol., 2005

Competing provers yield improved Karp-Lipton collapse results.

[BibT_eX]

[DOI]

Lane A. Hemaspaandra

Mitsunori Ogihara

Inf. Comput., 2005

Simulating Undirected st-Connectivity Algorithms on Uniform JAGs and NNJAGs.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 16th International Symposium, 2005

A Note on Zero Error Algorithms Having Oracle Access to One NP Query.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, 11th Annual International Conference, 2005

2004

On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy.

[BibT_eX]

[DOI]

SIAM J. Comput., 2004

Relativized collapsing between BPP and PH under stringent oracle access.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2004

A note on quadratic residuosity and UP.

[BibT_eX]

[DOI]

Robert A. Threlfall

Inf. Process. Lett., 2004

On Higher Arthur-Merlin Classes.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2004

Mass Spectrum Labeling: Theory and Practice.

[BibT_eX]

[DOI]

Proceedings of the 4th IEEE International Conference on Data Mining (ICDM 2004), 2004

2003

On testing for zero polynomials by a set of points with bounded precision.

[BibT_eX]

[DOI]

Eric Bach

Theor. Comput. Sci., 2003

A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor.

[BibT_eX]

[DOI]

Discret. Appl. Math., 2003

Estimation of Congestion Price Using Probabilistic Packet Marking.

[BibT_eX]

[DOI]

Proceedings of the Proceedings IEEE INFOCOM 2003, The 22nd Annual Joint Conference of the IEEE Computer and Communications Societies, San Franciso, CA, USA, March 30, 2003

X-Diff: An Effective Change Detection Algorithm for XML Documents.

[BibT_eX]

[DOI]

Yuan Wang

David J. DeWitt

Proceedings of the 19th International Conference on Data Engineering, 2003

Stringent Relativization.

[BibT_eX]

[DOI]

Proceedings of the FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science, 2003

On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy: Positive and Negative Results.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, 9th Annual International Conference, 2003

2002

On the Minimum Volume of a Perturbed Unit Cube.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 13th International Symposium, 2002

2001

S_2p \subseteq ZPPNP

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2001

Essentially every unimodular matrix defines an expander

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2001

On the Complexity of Join Predicates.

[BibT_eX]

[DOI]

Raghav Kaushik

Jeffrey F. Naughton

Proceedings of the Twentieth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2001

Sp2 subseteq ZPPNP.

[BibT_eX]

[DOI]

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

On the Average-Case Hardness of CVP.

[BibT_eX]

[DOI]

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

2000

Resolution of Hartmanis' conjecture for NL-hard sparse sets.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2000

The Complexity of the A B C Problem.

[BibT_eX]

[DOI]

Yechezkel Zalcstein

SIAM J. Comput., 2000

A note on the non-NP-hardness of approximate lattice problems under general Cook reductions.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2000

Essentially Every Unimodular Matrix Defines and Expander.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 11th International Conference, 2000

The Complexity of Some Lattice Problems.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Number Theory, 4th International Symposium, 2000

1999

Fine Separation of Average-Time Complexity Classes.

[BibT_eX]

[DOI]

Alan L. Selman

SIAM J. Comput., 1999

Robust Reductions.

[BibT_eX]

[DOI]

Lane A. Hemaspaandra

Gerd Wechsung

Theory Comput. Syst., 1999

Sparse Hard Sets for P: Resolution of a Conjecture of Hartmanis.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1999

Approximating the SVP to within a Factor (1+1/dimxi) Is NP-Hard under Randomized Reductions.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1999

A Classification of the Probabilistic Polynomial Time Hierarchy Under Fault Tolerant Access to Oracle Classes.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1999

A Lattice-Based Public-Key Cryptosystem.

[BibT_eX]

[DOI]

Thomas W. Cusick

Inf. Comput., 1999

Circuit Minimization Problem

[BibT_eX]

[DOI]

Valentine Kabanets

Electron. Colloquium Comput. Complex., 1999

Some Recent Progress on the Complexity of Lattice Problems

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1999

Foreword.

[BibT_eX]

[DOI]

C. K. Wong

Algorithmica, 1999

Hardness and Hierarchy Theorems for Probabilistic Quasi-Polynomial Time.

[BibT_eX]

[DOI]

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

On the Hardness of Permanent.

[BibT_eX]

[DOI]

Aduri Pavan

Proceedings of the STACS 99, 1999

On Routing in Circulant Graphs.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, 5th Annual International Conference, 1999

A New Transference Theorem in the Geometry of Numbers.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, 5th Annual International Conference, 1999

Applications of a New Transference Theorem to Ajtai's Connection Factor.

[BibT_eX]

[DOI]

Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

1998

A Relation of Primal-Dual Lattices and the Complexity of Shortest Lattice Vector Problem.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1998

Frobenius's Degree Formula and Toda's Polynomials.

[BibT_eX]

[DOI]

Theory Comput. Syst., 1998

Efficient Algorithms for a Scheduling Problem and its Applications to Illicit Drug Market Crackdowns.

[BibT_eX]

[DOI]

Pu Cai

Ashish V. Naik

J. Comb. Optim., 1998

On A Scheduling Problem of Time Deteriorating Jobs.

[BibT_eX]

[DOI]

Pu Cai

Yixin Zhu

J. Complex., 1998

A new transference theorem and applications to Ajtai's connection factor

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1998

Approximating the SVP to within a Factor is NP-Hard under Randomized Reductions.

[BibT_eX]

[DOI]

Proceedings of the 13th Annual IEEE Conference on Computational Complexity, 1998

1997

Approximating the SVP to within a factor (1 + 1/dimepsilon) is NP-hard under randomized reductions

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1997

Constant Depth Circuits and the Lutz Hypothesis.

[BibT_eX]

[DOI]

Martin Strauss

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

An Improved Worst-Case to Average-Case Connection for Lattice Problems.

[BibT_eX]

[DOI]

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

On the 100% Rule of Sensivity Analzsis in Linear Programming.

[BibT_eX]

[DOI]

Pu Cai

Proceedings of the Computing and Combinatorics, Third Annual International Conference, 1997

1996

The Bounded Membership Problem of the Monoid SL_2(N).

[BibT_eX]

[DOI]

Zicheng Liu

Math. Syst. Theory, 1996

On the Correlation of Symmetric Functions.

[BibT_eX]

[DOI]

Frederic Green

Thomas Thierauf

Math. Syst. Theory, 1996

On the Existence of Hard Sparse Sets under Weak Reductions.

[BibT_eX]

[DOI]

Ashish V. Naik

Proceedings of the STACS 96, 1996

Multiplicative Equations over Commuting Matrices.

[BibT_eX]

[DOI]

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

1995

On the Impossibility of Amplifying the Independence of Random Variables.

[BibT_eX]

[DOI]

Suresh Chari

Random Struct. Algorithms, 1995

Average Time Complexity Classes

[BibT_eX]

[DOI]

Alan L. Selman

Electron. Colloquium Comput. Complex., 1995

Pseudorandom Generators, Measure Theory, and Natural Proofs

[BibT_eX]

[DOI]

Kenneth W. Regan

Electron. Colloquium Comput. Complex., 1995

Communication Complexity of Key Agreement on Small Ranges.

[BibT_eX]

[DOI]

Proceedings of the STACS 95, 1995

The Resolution of a Hartmanis Conjecture.

[BibT_eX]

[DOI]

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

1994

Subquadratic Simulations of Balanced Formulae by Branching Programs.

[BibT_eX]

[DOI]

SIAM J. Comput., 1994

On Hausdorff and Topological Dimensions of the Kolmogorov Complexity of the Real Line.

[BibT_eX]

[DOI]

Juris Hartmanis

J. Comput. Syst. Sci., 1994

PSPACE Is Provable by Two Provers in One Round.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1994

Computing Jordan Normal Forms Exactly for Commuting Matrices in Polynomial Time.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 1994

Efficient Average-Case Algorithms for the Modular Group

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1994

Reliable Benchmarks Using Numerical Instability.

[BibT_eX]

[DOI]

Sigal Ar

Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

Rotation Distance, Triangulations of Planar Surfaces and Hyperbolic Geometry.

[BibT_eX]

[DOI]

Michael D. Hirsch

Proceedings of the Algorithms and Computation, 5th International Symposium, 1994

The Complexity of the Membership Problem for 2-generated Commutative Semigroups of Rational Matrices

[BibT_eX]

[DOI]

Yechezkel Zalcstein

Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

1993

Taking Random Walks to Grow Trees in Hypercubes.

[BibT_eX]

[DOI]

Sandeep N. Bhatt

J. ACM, 1993

Towards Uncheatable benchmarks.

[BibT_eX]

[DOI]

Proceedings of the Eigth Annual Structure in Complexity Theory Conference, 1993

1992

On Games of Incomplete Information.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1992

An optimal lower bound on the number of variables for graph identification.

[BibT_eX]

[DOI]

Martin Fürer

Neil Immerman

Comb., 1992

Parallel Computation Over Hyperbolic Groups

[BibT_eX]

[DOI]

Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

Promise Problems and Access to Unambiguous Computation.

[BibT_eX]

[DOI]

Jozef Vyskoc

Proceedings of the Mathematical Foundations of Computer Science 1992, 1992

Promise Problems and Guarded Access to Unambiguous Computation.

[BibT_eX]

Jozef Vyskoc

Proceedings of the Complexity Theory: Current Research, 1992

1991

A Note on Enumarative Counting.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1991

PSPACE Survives Constant-Width Bottlenecks.

[BibT_eX]

[DOI]

Merrick L. Furst

Int. J. Found. Comput. Sci., 1991

Computations Over Infinite Groups.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 8th International Symposium, 1991

1990

A Note on the Determinant and Permanent Problem

[BibT_eX]

[DOI]

Inf. Comput., January, 1990

On the Power of Parity Polynomial Time.

[BibT_eX]

[DOI]

Math. Syst. Theory, 1990

Lower Bounds for Constant-Depth Circuits in the Presence of Help Bits.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1990

Playing Games of Incomplete Information.

[BibT_eX]

[DOI]

Proceedings of the STACS 90, 1990

On Bounded Round Multi-Prover Interactive Proof Systems.

[BibT_eX]

[DOI]

Proceedings of the Proceedings: Fifth Annual Structure in Complexity Theory Conference, 1990

1989

Enumerative Counting Is Hard

[BibT_eX]

[DOI]

Inf. Comput., July, 1989

The Boolean Hierarchy II: Applications.

[BibT_eX]

[DOI]

SIAM J. Comput., 1989

With Probability One, a Random Oracle Separates PSPACE from the Polynomial-Time Hierarchy.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1989

Subquadratic Simulations of Circuits by Branching Programs

[BibT_eX]

[DOI]

Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

The Complexity Of The Real Line Is A Fractal.

[BibT_eX]

[DOI]

Juris Hartmanis

Proceedings of the Proceedings: Fourth Annual Structure in Complexity Theory Conference, 1989

1988

The Boolean Hierarchy I: Structural Properties.

[BibT_eX]

[DOI]

SIAM J. Comput., 1988

Take a Walk, Grow a Tree (Preliminary Version)

[BibT_eX]

[DOI]

Sandeep N. Bhatt

Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

1987

Graph Minimal Uncolorability is D^P-Complete.

[BibT_eX]

[DOI]

Gabriele E. Meyer

SIAM J. Comput., 1987

Probability One Separation of the Boolean Hierarchy.

[BibT_eX]

[DOI]

Proceedings of the STACS 87, 1987

On the Complexity of Graph Critical Uncolorability.

[BibT_eX]

[DOI]

Gabriele E. Meyer

Proceedings of the Automata, Languages and Programming, 14th International Colloquium, 1987

PSPACE survives three-bit bottlenecks.

[BibT_eX]

[DOI]

Merrick L. Furst

Proceedings of the Second Annual Conference on Structure in Complexity Theory, 1987

1986

On Some Most Probable Separations of Complexity Classes.

[BibT_eX]

PhD thesis, 1986

The Boolean Hierarchy: Hardware over NP.

[BibT_eX]

[DOI]