Article

The recognition problem for the set of perfect squares

Author:

Alan CobhamAuthors Info & Claims

SWAT '66: Proceedings of the 7th Annual Symposium on Switching and Automata Theory (swat 1966)

Pages 78 - 87

https://doi.org/10.1109/SWAT.1966.30

Published: 26 October 1966 Publication History

Publisher Site

Abstract

Lower bounds on the capacity and on the product of capacity and computation time are obtained for machines which recognize the set of squares. The bound on capacity is approached to within a factor of four by a specific machine which carries out a test based on the fact that every non-square is a quadratic non-residue of some rational prime. A machine which carries out a test based on the standard root-extraction algorithm is substantially less efficient in this respect. For neither machine is the bound on the capacity-time product closely approached.

Cited By

View all

Beame PGrosshans NMcKenzie PSegoufin L(2016)Nondeterminism and An Abstract Formulation of Nečiporuk’s Lower Bound MethodACM Transactions on Computation Theory10.1145/30135169:1(1-34)Online publication date: 26-Dec-2016
https://dl.acm.org/doi/10.1145/3013516
Zhang B(2011)Generic constant-round oblivious sorting algorithm for MPCProceedings of the 5th international conference on Provable security10.5555/2042756.2042777(240-256)Online publication date: 16-Oct-2011
https://dl.acm.org/doi/10.5555/2042756.2042777
Chan T(2010)Comparison-based time-space lower bounds for selectionACM Transactions on Algorithms10.1145/1721837.17218426:2(1-16)Online publication date: 6-Apr-2010
https://dl.acm.org/doi/10.1145/1721837.1721842
Show More Cited By

Recommendations

Perfect secrecy, perfect omniscience and steiner tree packing
ISIT'09: Proceedings of the 2009 IEEE international conference on Symposium on Information Theory - Volume 2

We investigate perfect secret key generation for a "pairwise independent network" model in which every pair of terminals observes correlated sources that are independent of sources observed by all other pairs of terminals. The terminals are then allowed ...
Perfect omniscience, perfect secrecy, and Steiner tree packing

We consider perfect secret key generation for a "pairwise independent network" model in which every pair of terminals share a random binary string, with the strings shared by distinct terminal pairs being mutually independent. The terminals are then ...
New families of atomic Latin squares and perfect 1-factorisations

A perfect 1-factorisation of a graph G is a decomposition of G into edge disjoint 1-factors such that the union of any two of the factors is a Hamiltonian cycle. Let p ≥ 11 be prime. We demonstrate the existence of two non-isomorphic perfect 1-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SWAT '66: Proceedings of the 7th Annual Symposium on Switching and Automata Theory (swat 1966)

October 1966

298 pages

Publisher

IEEE Computer Society

United States

Publication History

Published: 26 October 1966

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 23 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Beame PGrosshans NMcKenzie PSegoufin L(2016)Nondeterminism and An Abstract Formulation of Nečiporuk’s Lower Bound MethodACM Transactions on Computation Theory10.1145/30135169:1(1-34)Online publication date: 26-Dec-2016
https://dl.acm.org/doi/10.1145/3013516
Zhang B(2011)Generic constant-round oblivious sorting algorithm for MPCProceedings of the 5th international conference on Provable security10.5555/2042756.2042777(240-256)Online publication date: 16-Oct-2011
https://dl.acm.org/doi/10.5555/2042756.2042777
Chan T(2010)Comparison-based time-space lower bounds for selectionACM Transactions on Algorithms10.1145/1721837.17218426:2(1-16)Online publication date: 6-Apr-2010
https://dl.acm.org/doi/10.1145/1721837.1721842
Chan TMathieu C(2009)Comparison-based time-space lower bounds for selectionProceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms10.5555/1496770.1496787(140-149)Online publication date: 4-Jan-2009
https://dl.acm.org/doi/10.5555/1496770.1496787
Cook S(2007)An overview of computational complexityACM Turing award lectures10.1145/1283920.1283938Online publication date: 1-Jan-2007
https://dl.acm.org/doi/10.1145/1283920.1283938
Wegener I(2004)BDDs-design, analysis, complexity, and applicationsDiscrete Applied Mathematics10.5555/1704845.1705111138:1-2(229-251)Online publication date: 1-Mar-2004
https://dl.acm.org/doi/10.5555/1704845.1705111
Klauck H(2004)Quantum and classical communication-space tradeoffs from rectangle boundsProceedings of the 24th international conference on Foundations of Software Technology and Theoretical Computer Science10.1007/978-3-540-30538-5_32(384-395)Online publication date: 16-Dec-2004
https://dl.acm.org/doi/10.1007/978-3-540-30538-5_32
Sauerhoff M(2003)Approximation of boolean functions by combinatorial rectanglesTheoretical Computer Science10.5555/2780704.2781148301:1(45-78)Online publication date: 14-May-2003
https://dl.acm.org/doi/10.5555/2780704.2781148
Santhanam R(2001)Lower bounds on the complexity of recognizing SAT by turing machinesInformation Processing Letters10.1016/S0020-0190(00)00227-179:5(243-247)Online publication date: 1-Sep-2001
https://dl.acm.org/doi/10.1016/S0020-0190%2800%2900227-1
Shparlinski I(2000)Computing Jacobi Symbols modulo Sparse Integers and Polynomials and Some ApplicationsJournal of Algorithms10.1006/jagm.2000.109136:2(241-252)Online publication date: 1-Aug-2000
https://dl.acm.org/doi/10.1006/jagm.2000.1091
Show More Cited By

Abstract

Cited By

Recommendations

Perfect secrecy, perfect omniscience and steiner tree packing

Perfect omniscience, perfect secrecy, and Steiner tree packing

New families of atomic Latin squares and perfect 1-factorisations

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations