NDLI: Complexity Lower Bounds through Balanced Graph Properties

Content Provider	IEEE Xplore Digital Library
Author	Moshkovitz, G.
Copyright Year	2012
Abstract	We present a combinatorial approach for proving complexity lower bounds, we focus on the following instantiation of this approach. For a property of regular hyper graphs with $m$ edges and an arbitrary hyper graph $G$ with $m-t$ edges, we may count the number of super-hyper graphs of $G$ (i.e., hyper graphs obtained by adding $t$ edges) satisfying the property. Suppose that we find a pair of these properties where every such $G$ has the same number of super-hyper graphs satisfying each property. We show that in this case, we immediately obtain an explicit $m/(t-1)$ lower bound on the rank of tensors (which are high-dimensional matrices). Notice that if the hyper graphs are $3$-uniform, this implies a lower bound of $\Omega(m/t)$ for arithmetic circuits. We also show, albeit non-explicitly, that essentially-optimal lower bounds can be obtained using this approach. Furthermore, we exemplify our approach in the $t=2$ case, and prove that even in this case we can already obtain interesting lower bounds. In particular, we derive a (tight) lower bound of $3n/2$ on the rank of $n\times n\times n$ tensors that are naturally associated with hyper graph trees. In fact, our bound also applies to the stronger notion of {\em border} rank, for which our result essentially matches the best lower bounds known.
Starting Page	159
Ending Page	169
File Size	294809
Page Count	11
File Format	PDF
ISBN	9781467316637
ISSN	10930159
e-ISBN	9780769547084
DOI	10.1109/CCC.2012.31
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2012-06-26
Publisher Place	Portugal
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Tensile stress Polynomials Complexity theory Upper bound Computational modeling Vegetation Educational institutions tensor rank arithmetic circuits lower bounds
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Libarray of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Tensor Rank: Some Lower and Upper Bounds

Recent Progress on Lower Bounds for Arithmetic Circuits

On the Power of Homogeneous Depth 4 Arithmetic Circuits

Tensor-rank and lower bounds for arithmetic formulas

An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas

Lower bounds for matrix product

The Proof Complexity of Polynomial Identities

Multiparty Communication Complexity and Threshold Circuit Size of AC^0

The Maximum Communication Complexity of Multi-Party Pointer Jumping

Complexity Lower Bounds through Balanced Graph Properties

Similar Documents

Tensor Rank: Some Lower and Upper Bounds

Recent Progress on Lower Bounds for Arithmetic Circuits

On the Power of Homogeneous Depth 4 Arithmetic Circuits

Tensor-rank and lower bounds for arithmetic formulas

An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas

Lower bounds for matrix product

The Proof Complexity of Polynomial Identities

Multiparty Communication Complexity and Threshold Circuit Size of AC^0

The Maximum Communication Complexity of Multi-Party Pointer Jumping

Complexity Lower Bounds through Balanced Graph Properties