from    
to    
search  

 


Symmetry restoration and quantum Mpemba effects in chaotic andlocalization sy...
Quantum Gases 2024
Stories of Fermions in an Optical Box
Contractive Unitary and Classical Shadow Tomography
报告题目:
Matrix Rank, Rigidity and Complexity
 报告人:
Jayalal Sarma M.N.
ITCS, Tsinghua University
报告时间:
2008-03-05 11:00
报告地点:
Room 4-603, FIT Building, Tsinghua University
主办单位:
ITCS, Tsinghua University
  简介:

 

In this talk we revisit the interplay between some linear algebraic concepts and circuit complexity theory. We will provide some new characterisations of complexity classes in terms of matrix rank computation. We consider the problem of optimizing matrix rank, a version of which is related to the notion of matrix rigidity: the number of entries that needs to be changed in the matrix to bring down the rank below a specified value is therigidity of a matrix. Matrices with high rigidity have interesting applications in the theory of lowerbounds: mainly in arithmetic circuits and in communication complexity. We will briefly mention some of our recent results in this context, and discuss some complexity theoretic results (and some open ends) for the computational version of the problem.

l           个人简介:

Jayalal Sarma M.N. is a Ph.D student for Theoretical Computer Science in The Institute of Mathematical Sciences in India, under the guidance of Prof. Meena Mahajan.

His academic interests are mainly in Computational Complexity theory.

l           学科分类:计算机科学与技术

今日相关信息
《三联生活周刊》的知识生产
IBM Strategy of SOA Solution
基本法是如何产生的
 
同类别相关信息
动物伦理学与护生文化系列讲座:做一个有...
从创新到卓越:知本家冯冠平
FULL-COVERAGE FILM COOLING, and OVE...
科学引文分析及其意义
清华信息大讲堂第85讲-NEC论坛第2讲
学术活动