Follow
Martin Fürer
Martin Fürer
Professor of Computer Science and Engineering, Pennsylvania State University
Verified email at cse.psu.edu - Homepage
Title
Cited by
Cited by
Year
An optimal lower bound on the number of variables for graph identification
JY Cai, M Fürer, N Immerman
Combinatorica 12 (4), 389-410, 1992
7971992
Faster Integer Multiplication
M Fürer
Proceedings of the Thirty-Ninth Symposium on Theory of Computing, 57-66, 2007
6232007
Approximating the minimum-degree Steiner tree to within one of optimal
M Furer, B Raghavachari
Journal of Algorithms 17 (3), 409-423, 1994
2701994
Approximation of k-set cover by semi-local optimization
R Duh, M Fürer
Proceedings of the twenty-ninth annual ACM symposium on Theory of computing …, 1997
2201997
Approximating the minimum degree spanning tree to within one from the optimal degree
M Fürer, B Raghavachari
Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms …, 1992
1781992
On completeness and soundness in interactive proof systems
M Furer, O Goldreich, Y Mansour, M Sipser, S Zachos
Advances in Computing Research 5, 429-442, 1989
1391989
Approximating maximum independent set in bounded degree graphs
P Berman, M Fürer
Proceedings of the fifth annual ACM-SIAM Symposium on discrete algorithms …, 1994
1321994
Algorithms for Counting 2-Sat Solutions and Colorings with Applications
M Fürer, SP Kasiviswanathan
Algorithmic Aspects in Information and Management: Third International …, 2007
782007
Probabilistic quantifiers vs. distrustful adversaries
S Zachos, M Furer
International Conference on Foundations of Software Technology and …, 1987
701987
The computational complexity of the unconstrained limited domino problem (with implications for logical decision problems)
M Fürer
Logic and Machines: Decision Problems and Complexity: Proceedings of the …, 1984
661984
On the combinatorial power of the Weisfeiler-Lehman algorithm
M Fürer
International Conference on Algorithms and Complexity, 260-271, 2017
562017
An NC approximation algorithm for minimum degree spanning tree problem
M Furer
Proc. of the 28th Annual Allerton Conf. on Communication, Control and …, 1990
561990
Normal forms for trivalent graphs and graphs of bounded valence
M Fürer, W Schnyder, E Specker
Proceedings of the fifteenth annual ACM symposium on Theory of computing …, 1983
471983
The complexity of Presburger arithmetic with bounded quantifier alternation depth
M Fürer
Theoretical Computer Science 18 (1), 105-111, 1982
451982
A faster algorithm for finding maximum independent sets in sparse graphs
M Fürer
LATIN 2006: Theoretical Informatics: 7th Latin American Symposium, Valdivia …, 2006
432006
The tight deterministic time hierarchy
M Fürer
Proceedings of the fourteenth annual ACM symposium on Theory of computing, 8-16, 1982
431982
Weisfeiler-Lehman refinement requires at least a linear number of iterations
M Fürer
Automata, Languages and Programming: 28th International Colloquium, ICALP …, 2001
422001
The complexity of the inequivalence problem for regular expressions with intersection
M Fürer
International Colloquium on Automata, Languages, and Programming, 234-245, 1980
421980
Improved hardness results for approximating the chromatic number
M Furer
Proceedings of IEEE 36th Annual Foundations of Computer Science, 414-421, 1995
391995
Alternation and the Ackermann case of the decision problem
M Fürer
L’Enseignement Math 27, 137-162, 1981
351981
The system can't perform the operation now. Try again later.
Articles 1–20