Computational Complexity and Local Algorithms: On the Interplay Between Randomness and Computation
暫譯: 計算複雜度與局部演算法：隨機性與計算之間的相互作用

Goldreich, Oded

Computational Complexity and Local Algorithms: On the Interplay Between Randomness and Computation
  • 出版商: Springer
  • 出版日期: 2025-06-10
  • 售價: $3,010
  • 貴賓價: 9.5 折 $2,860
  • 語言: 英文
  • 頁數: 451
  • 裝訂: Quality Paper - also called trade paper
  • ISBN: 3031889452
  • ISBN-13: 9783031889455
  • 相關分類: Algorithms-data-structures

    • 海外代購書籍(需單獨結帳)

相關主題

商品描述

This volume contains a collection of studies in the areas of complexity theory and local algorithms. A common theme in most of the papers is the interplay between randomness and computation. This interplay is pivotal to some parts of complexity theory and is essential for local algorithms.

The works included address a variety of topics in the areas of complexity theory and local algorithms. Within complexity theory the topics include approximation algorithms, counting problems, enumeration problems, explicit construction of expander graphs, fine grained complexity, interactive proof systems, PPT-search and pseudodeterminism, space complexity, and worst-case to average-case reductions. Within local algorithms the focus is mostly on property testing and on locally testable and decodable codes. In particular, many of the works seek to advance the study of testing graph properties in the bounded-degree graph model. Other topics in property testing include testing group properties and testing properties of affine subspaces.

商品描述(中文翻譯)

本卷包含了一系列關於複雜性理論和局部演算法的研究。大多數論文中的共同主題是隨機性與計算之間的相互作用。這種相互作用對於複雜性理論的某些部分至關重要，並且對於局部演算法也是必不可少的。

所包含的研究涵蓋了複雜性理論和局部演算法領域的各種主題。在複雜性理論中，主題包括近似演算法、計數問題、列舉問題、擴展圖的顯式構造、細粒度複雜性、互動證明系統、PPT-search 和偽確定性、空間複雜性，以及最壞情況到平均情況的簡化。在局部演算法中，重點主要放在性質測試以及局部可測試和可解碼的碼上。特別是，許多研究旨在推進在有界度圖模型中測試圖性質的研究。性質測試中的其他主題包括測試群性質和測試仿射子空間的性質。

作者簡介

Oded Goldreich is a Meyer W. Weisgal Professor at the Weizmann Institute of Science, Israel. Oded completed his graduate studies in 1983 under the supervision of Shimon Even, he was a postdoctoral fellow at MIT (1983-1986), a faculty member at the Technion (1986-1994), a visiting scientist at MIT (1995-1998), and a Radcliffe fellow at Harvard (2003-2004). Since 1995 he has been a member of the Computer Science and Applied Mathematics department at the Weizmann Institute. He is the author of "Modern Cryptography, Probabilistic Proofs and Pseudorandomness" (Springer, 1998), the two-volume work "Foundations of Cryptography" (Cambridge University Press, 2001, 2004), "Computational Complexity: A Conceptual Perspective" (Cambridge University Press, 2008), and "Introduction to Property Testing" (Cambridge University Press, 2017).

Nader H. Bshouty is a Professor of Computer Science at the Technion - Israel Institute of Technology, Israel. He completed his doctoral studies in Computer Science in 1989 at the Technion under the supervision of Michael Kaminski, from 1989 to 1998, he held academic positions at the University of Calgary, Canada. Since 1999, he has been a professor at the Technion. His research focuses on Computational Learning Theory, Property Testing, Models of Computation, and the Complexity of Algebraic Computations.

Dana Ron is the Lazarus Brothers Chair of Computer Engineering in the School of Electrical Engineering at Tel Aviv University, Israel. Dana completed her graduate studies in 1995 under the supervision of Naftali Tishby, she was an NSF postdoctoral fellow at MIT (1995-1997), a science scholar at the Bunting Institute, Radcliffe (1997-1998), and a Radcliffe fellow at Harvard (2003-2004). Since 1998 she has been a faculty member at Tel Aviv University. She is a fellow of the EATCS and ACM.

Laliv Tauber completed her master's thesis at the Weizmann Institute of Science in 2024.

作者簡介(中文翻譯)

Oded Goldreich 是以色列魏茨曼科學研究所的 Meyer W. Weisgal 教授。Oded 於 1983 年在 Shimon Even 的指導下完成研究生學業，隨後在麻省理工學院 (MIT) 擔任博士後研究員 (1983-1986)，之後在以色列理工學院 (Technion) 擔任教職 (1986-1994)，並於 1995 年至 1998 年期間擔任麻省理工學院的訪問科學家，2003 年至 2004 年擔任哈佛大學的 Radcliffe 研究員。自 1995 年以來，他一直是魏茨曼科學研究所計算機科學與應用數學系的成員。他是《現代密碼學、隨機性證明與偽隨機性》（Springer, 1998）、兩卷本的《密碼學基礎》（劍橋大學出版社, 2001, 2004）、《計算複雜性：概念視角》（劍橋大學出版社, 2008）以及《屬性測試導論》（劍橋大學出版社, 2017）的作者。

Nader H. Bshouty 是以色列理工學院 (Technion) 的計算機科學教授。他於 1989 年在以色列理工學院完成計算機科學博士學位，指導教授為 Michael Kaminski，並於 1989 年至 1998 年期間在加拿大卡爾加里大學擔任學術職位。自 1999 年以來，他一直是以色列理工學院的教授。他的研究重點包括計算學習理論、屬性測試、計算模型以及代數計算的複雜性。

Dana Ron 是以色列特拉維夫大學電機工程學院的 Lazarus Brothers 計算機工程講座教授。Dana 於 1995 年在 Naftali Tishby 的指導下完成研究生學業，並於 1995 年至 1997 年期間在麻省理工學院擔任 NSF 博士後研究員，1997 年至 1998 年期間在 Radcliffe 的 Bunting Institute 擔任科學學者，2003 年至 2004 年期間擔任哈佛大學的 Radcliffe 研究員。自 1998 年以來，她一直是特拉維夫大學的教職員。她是 EATCS 和 ACM 的會士。

Laliv Tauber 於 2024 年在魏茨曼科學研究所完成碩士論文。

類似商品