En matriss styvhet mäter antalet poster som måste ändras för att minska dess rang under ett visst värde. De kända nedre gränserna för de explicita matrisernas styvhet är mycket svaga. Det är känt att starkare lägre gränser skulle få konsekvenser för komplexitetsteorin. W e överväga svagare former av stelhetsproblem över de komplexa talen. Med hjälp av spektralmetoder får vi lägre gränser på dessa varianter. V e sedan ge två ansökningar av sådana svagare former. För det första visar vi att vår lägre gräns på en variant av styvhet innebär lägre gränser på storleksdjupa kompromisser för aritmetiska kretsar med avgränsade coeficens dator linjära transformationer. Dessa gränser generaliserar ett färskt resultat av Nisan och Wigderson. Den andra tillämpningen är villkorad; vi visar att det skulle vara utmärkt att bevisa lägre gränser på vissa svagare former av stelhet att ingå flera separation resultat i kommunikations komplexitet teori. Våra resultat kompletterar och stärker ett resultat av Razborov.
Lägre gränser på matris styvhet har tillämpningar för krets och kommunikation komplexitet REF.
Spectral methods for matrix rigidity with applications to size-depth tradeoffs and communication complexity
{'venue': 'Proceedings of IEEE 36th Annual Foundations of Computer Science', 'journal': 'Proceedings of IEEE 36th Annual Foundations of Computer Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}