%0 Journal Article
%T Progress in Computational Complexity Theory
%A Jin-Yi Cai
%A Hong Zhu
%A <br>Jin-Yi
%A Cai
%A and
%A Hong
%A Zhu
%J 计算机科学技术学报
%D 2005
%I 
%X We briefly survey a number of important recent achievements in Theoretical Computer Science (TCS), especially Computational Complexity Theory. We will discuss the PCP Theorem, its implications to inapproximability on combinatorial optimization problems; space bounded computations, especially deterministic logspace algorithm for undirected graph connectivity problem; deterministic polynomial-time primality test; lattice complexity, worst-case to average-case reductions; pseudorandomness and extractor constructions; and Valiant's new theory of holographic algorithms and reductions.
%K theoretical computer science
%K computational complexity theory
%K PCP theorem
%K inapproximability
%K logspace complexity
%K Reingold's theorem
%K GAP problem
%K primality testing
%K complexity of lattice problems
%K worst-case to average-case reductions
%K pseudorandomness
%K extractors
%K holographic algorithms<br>计算机科学
%K 复杂性
%K PCP
%K 优化组合
%K 伪随机性
%K 全息算法
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=F57FEF5FAEE544283F43708D560ABF1B&aid=A662ABBB73A54E1C90D246AFBD23092C&yid=2DD7160C83D0ACED&vid=A04140E723CB732E&iid=B31275AF3241DB2D&sid=B60458D1AE87BCD1&eid=626A0FE8E3130AB5&journal_id=1000-9000&journal_name=计算机科学技术学报&referenced_num=0&reference_num=72