@UNPUBLISHED{ref:Che05,
  author =	 {Mahdi Cheraghchi},
  title =	 {On Matrix Rigidity and the Complexity of Linear
                  Forms},
  year =	 2005,
  note =	 {ECCC Technical Report TR05-070.},
  abstract =	 { The rigidity function of a matrix is defined as the
                  minimum number of its entries that need to be
                  changed in order to reduce the rank of the matrix to
                  below a given parameter. Proving a strong enough
                  lower bound on the rigidity of a matrix implies a
                  nontrivial lower bound on the complexity of any
                  linear circuit computing the set of linear forms
                  associated with it. However, although it is shown
                  that most matrices are rigid enough, no explicit
                  construction of a rigid family of matrices is known.
                  We review the concept of rigidity and some of its
                  interesting variations as well as several notable
                  works related to that. We also show the existence of
                  highly rigid matrices constructed by evaluation of
                  bivariate polynomials over a finite field.  },
  keywords =	 {Matrix Rigidity, Low Level Complexity, Circuit
                  Complexity, Linear Forms}
}

{"_id":"Yo3HXfyb6k7ep3fBN","bibbaseid":"cheraghchi-onmatrixrigidityandthecomplexityoflinearforms-2005","authorIDs":["2n8MNophuzbeevTa8","3NEcSaujokmJYSDaa","3tFWxWs2qWeYAZx9a","4QNcMTdRiWr2gs8Sk","5KoQWR3vSjnsoZNz5","5i4QHRc5LGio8Mf5u","62bYDgAFwCxaQ4Q9T","685mTysGDdQJKGxEE","6sX76eTffL7p76peN","8NLx3B3FAvaK54hSK","9NZpjMJLG7dNWroGm","9aD4MPX9ELhsyJmaR","9aFgrqcc4j28kZn8n","A9wAgP7TPK9tw28qY","BJ6h7zrsT3L89RKSg","BWL9E9QxvrST7y7ym","Cht4qGZ9eYAvPygNC","D3NMRJpac7Z2oFz7x","EiL6Xv4GTWGB97B8H","F3Y934eNyTeEJsg6E","FDEj5Zwdm28pFcAnB","FJdyLy2TL3v973ge8","GxccwstJJuJ4rg7Dq","HP7szFXWBWFXXZhdA","HRX7xsd7ZkTNvr67D","Hj3KN5PTNMST8hD3b","JEvEPvDBYNNXgGBnp","JYpde2ppjXLva6cre","KFgC2dZG7jXYAgZ3T","NRg9mmaSB55QqzNnH","NWCEkq6XqRBCiGmMe","NpGaG45evixRFDMiF","NyDiXeBc7cuxdWrqh","P6pva6vpPZCz6ndh9","Py2jfYGNZKNt7nxL6","Q6E9aDkYPcbhngLMx","QYrXKExv3BPABZGyA","QupQWsidagmv2nu8Z","SGZ2YignSm7njeTxy","SSuyWxzudqBDgAosw","THz3CmRmH3zZ9Xfud","TTEBJzPHwrY4d2Qfi","Wzr7kB4bxMDqceidA","YedfCw6zcDLoWAWFL","YtTEuSL9GJ8pkKcZw","Z3w2d32WjDczZMeGo","aduB2YE7dcNtbHnAN","c8gPvTXFPd9NazgEw","d6HAadRZAtz97Y2so","dTBDNYCcYKNNdhqaR","ezDt3Lb3Q6Sbo2rfX","fXtxgjbjZswBmF45i","ftBpmnKRHoB2muB8u","gKxHau44e8gnmxs6v","hM29eSWZbASnmDdFf","hw7Q4GHDAHkLTAyeB","i6Ns5rSW8R3ifxeHg","jJcoL4QWRkJQ59LfW","kKvRZ55rH7sfbubS2","kdfqsAMqCFDhpuW3S","koPTGcsAkwhGbkAYe","manxWg6Q3ZC5vW4JE","pwN2yYKo5DdSDaZGs","qpSgMrJ8WQNupjbXX","sD5Wq95oeSzqGF9kn","uSGLWGoXjyDyozeEy","wCcpScxkvg5RkcmWm","xKz7kx4eXbnkHeNXP","xeiij9YsbXBbMjciP","yGxZz3yuu6krMRxgK","yjJrpKY5QmDe8SXvm","zaR6PwJ7aC9xWBpiy"],"author_short":["Cheraghchi, M."],"bibdata":{"bibtype":"unpublished","type":"unpublished","author":[{"firstnames":["Mahdi"],"propositions":[],"lastnames":["Cheraghchi"],"suffixes":[]}],"title":"On Matrix Rigidity and the Complexity of Linear Forms","year":"2005","note":"ECCC Technical Report TR05-070.","abstract":"The rigidity function of a matrix is defined as the minimum number of its entries that need to be changed in order to reduce the rank of the matrix to below a given parameter. Proving a strong enough lower bound on the rigidity of a matrix implies a nontrivial lower bound on the complexity of any linear circuit computing the set of linear forms associated with it. However, although it is shown that most matrices are rigid enough, no explicit construction of a rigid family of matrices is known. We review the concept of rigidity and some of its interesting variations as well as several notable works related to that. We also show the existence of highly rigid matrices constructed by evaluation of bivariate polynomials over a finite field. ","keywords":"Matrix Rigidity, Low Level Complexity, Circuit Complexity, Linear Forms","bibtex":"@UNPUBLISHED{ref:Che05,\n author =\t {Mahdi Cheraghchi},\n title =\t {On Matrix Rigidity and the Complexity of Linear\n Forms},\n year =\t 2005,\n note =\t {ECCC Technical Report TR05-070.},\n abstract =\t { The rigidity function of a matrix is defined as the\n minimum number of its entries that need to be\n changed in order to reduce the rank of the matrix to\n below a given parameter. Proving a strong enough\n lower bound on the rigidity of a matrix implies a\n nontrivial lower bound on the complexity of any\n linear circuit computing the set of linear forms\n associated with it. However, although it is shown\n that most matrices are rigid enough, no explicit\n construction of a rigid family of matrices is known.\n We review the concept of rigidity and some of its\n interesting variations as well as several notable\n works related to that. We also show the existence of\n highly rigid matrices constructed by evaluation of\n bivariate polynomials over a finite field. },\n keywords =\t {Matrix Rigidity, Low Level Complexity, Circuit\n Complexity, Linear Forms}\n}\n\n","author_short":["Cheraghchi, M."],"key":"ref:Che05","id":"ref:Che05","bibbaseid":"cheraghchi-onmatrixrigidityandthecomplexityoflinearforms-2005","role":"author","urls":{},"keyword":["Matrix Rigidity","Low Level Complexity","Circuit Complexity","Linear Forms"],"metadata":{"authorlinks":{"cheraghchi, m":"https://mahdi.ch/"}}},"bibtype":"unpublished","biburl":"http://mahdi.ch/writings/cheraghchi.bib","creationDate":"2020-05-29T16:57:42.906Z","downloads":0,"keywords":["matrix rigidity","low level complexity","circuit complexity","linear forms"],"search_terms":["matrix","rigidity","complexity","linear","forms","cheraghchi"],"title":"On Matrix Rigidity and the Complexity of Linear Forms","year":2005,"dataSources":["YZqdBBx6FeYmvQE6D"]}