Modified ranks of tensors and the size of circuits

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Modified ranks of tensors and the size of circuits

Full text

Pdf (803 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing table of contents

San Diego, California, United States

Pages: 523 - 531

Year of Publication: 1993

ISBN:0-89791-591-7

Authors

P. Pudlák
V. Rödl

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 21, Citation Count: 4

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/167088.167228 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	M. Ajtai, J. KomlSs, E. Szemer#di, A note on Ramsey numbers, J. Comb. Theor. (A), 29, 1980, 354-360.
	2	N. Alon, P. Pudl~k, Superconcentrators of depth 2 and 3; odd levels help (rarely), to appear in Journ. of ACM.
	3	N. Alon, J. Spencer, The Probabilistic Method, Wiley, 1991.
	4	B. Bollob#s, Random Graphs, Academic Press 1985.
	5	B. Bollob#s, The chromatic number of random graphs, Combinatorica 8,(1), 1988, 49-55.
	6	B. Bollob#s, P. ErdSs, Cliques in random grapt# Math. Proc. Camb. Phil. Soc. 80, (1976), 419-417.
	7	Danny Dolev , Cynthia Dwork , Nicholas Pippenger , Avi Wigderson, Superconcentrators, generalizers and generalized connectors with limited depth, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.42-51, December 1983 [doi>10.1145/800061.808731]
	8	J. Friedman, A note on matrix rigidity, 1990, preprint.
	9	Hans F. de Groote, Lectures on the complexity of bilinear problems, Springer-Verlag New York, Inc., New York, NY, 1987
	10	S. Janson, T. Luczak, A. Rucifiski, An exponential bound for the probability of nonexistence of a specified subgraph in a random graph, in Random Graphs'87, M. Karofiski et al. eds., Wiley, 1990, 73-87.
	11	Noam Nisan , Avi Widgerson, Rounds in communication complexity revisited, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.419-429, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103463]
	12	N. Pippenger, A.C.-C. Yao, Rearrangeable networks with limited depth, SIAM J. Alg. Distr. Methods 3, 1982, 411-417.
	13	P. Pudl~k, Communication in bounded depth circuits, to appear in Combinatorica.
	14	P. Pudl#k, P. Savick#, On shifting networks, to appear in Theor. Computer Sci.
	15	A.A. Razborov, On rigid matrices, preprint (Russian).
	16	J. Sgall, A note on multyparty communication complexity of shifts, manuscript.
	17	V. Strassen, Vermeidung yon Divisionen, Crelles J. Reine Angew. Math. 264, 1973, 184-202.
	18	L.G. Valiant, Graph-theoretic arguments in low level complexity, MFCS 1977, Springer-verlag LNCS, 162-176.
	19	Leslie G. Valiant, Why is Boolean complexity theory difficult?, Poceedings of the London Mathematical Society symposium on Boolean function complexity, p.84-94, December 1992, London, United Kingdom
	20	A. Wigderson- private communication.

CITED BY 5

	Satyanarayana V. Lokam, Complexity Lower Bounds using Linear Algebra, Foundations and Trends® in Theoretical Computer Science, v.4 n.1–2, p.1-155, January 2009
	Benny Chor , Eyal Kushilevitz , Oded Goldreich , Madhu Sudan, Private information retrieval, Journal of the ACM (JACM), v.45 n.6, p.965-981, Nov. 1998
	Claudia Bertram-Kretzberg , Thomas Hofmeister , Hanno Lefmann, Sparse 0-1-matrices and forbidden hypergraphs, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.181-187, January 25-27, 1998, San Francisco, California, United States
	Claudia Bertram-Kretzberg , Hanno Lefmann, The algorithmic aspects of uncrowded hypergraphs, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.296-304, January 05-07, 1997, New Orleans, Louisiana, United States
	Omer Barkol , Yuval Ishai , Enav Weinreb, Communication in the presence of replication, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada