Главная    Ex Libris    Книги    Журналы    Статьи    Серии    Каталог    Wanted    Загрузка    ХудЛит    Справка    Поиск по индексам    Поиск    Форум   
blank
Авторизация

       
blank
Поиск по указателям

blank
blank
blank
Красота
blank
Sudan M. — Efficient Checking of Polynomials and Proofs and the Hardness of Approximation Problems
Sudan M. — Efficient Checking of Polynomials and Proofs and the Hardness of Approximation Problems



Обсудите книгу на научном форуме



Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter


Название: Efficient Checking of Polynomials and Proofs and the Hardness of Approximation Problems

Автор: Sudan M.

Аннотация:

This book is based on the author's PhD thesis which was selected as the winning thesis of the 1993 ACM Doctoral Dissertation Competition. The author improved the presentation and included the progress achieved since the thesis was approved by the University of California at Berkeley.
This work is a fascinating piece of theoretical computer science research building on deep results from different areas. It provides new theoretical insights and advances applicable techniques in such different areas as computational complexity, efficient (randomized) checking of proofs, programs and polynomials, approximation algorithms, NP-complete optimization, and error-detection and error-correction algorithms in coding theory.


Язык: en

Рубрика: Математика/

Статус предметного указателя: Готов указатель с номерами страниц

ed2k: ed2k stats

Год издания: 1996

Количество страниц: 87

Добавлена в каталог: 16.11.2009

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID
blank
Предметный указатель
Approximation by polynomials      46
Approximation preserving reductions      61
Checker      6 9
CLOSE      15
Constraint satisfaction problem      64
Curve      16 18
Distance      2
Distance to function family      8
Distance, absolute      9
Distance, between functions      15
Distance, relative      9
Encoding scheme      51 52 55
Error-correction      9
Error-detection      9
Evenly spaced points      26
Evenly spaced test      29 31
Hadamard Codes      10
Hardness of approximation, chromatic number      61
Hardness of approximation, clique size      14 62
Hardness of approximation, MAX SNP      14 67
L-reduction      62 64
Linear corrector      54
Linearity      8 53
Linearity testing      54
lines      16 34
Longest path      66
MAX 2 SAT      65
MAX 3 SAT      65
MAX CLIQUE      66
MAX CUT      65
MAX PCP      66
MAX SNP      14 62 64—67
Neighborhood      3 23 24
Neighborhood constraint      24
Optimization problem      62
Oracle      4 12
Pairwise independence      20
PCP      49 62
Permanent      9 22 41
Polynomial Evaluation Codes      11
Polynomial Extension Codes      11 52 84
Polynomial with help      4 42
Polynomial, construction rule      5 40 50 52 84 85
Polynomial, distance      2
Polynomial, implicit      23
Polynomial, multivariate      21 41
Polynomial, random self-reducibility      17
Polynomial, reconstruction      21
Polynomial, satisfiability      5 43
Polynomial, self-correction      2 11
Polynomial, specific      40
Polynomial, testing      3 23
Polynomial, univariate      25
proof      1
Proof, interactive      12
Proof, multiprover interactive      8 12 58
Proof, probabilistically checkable      1 13 48
Proof, transparent      12 48
Prover      4
PTAS      63
Query complexity      13 49 57
Random self-reducibility      8 16 22
Randomness complexity      13 49
Recursive proof checking      50 53 57 81
Reed Solomon Codes      10
Resilience      15
RPCP      51 53 57 81
Sapproximation      63
Segmented proofs      50 51
Self-corrector      1 7 16
Self-tester      1 7
Self-testing/correcting, function family      8
SHORTEST SUPERSTRING, SNP      64
Steiner tree      66
Verifier      1 4
Verifier, probabilistic      12
Vertex cover      65
blank
Реклама
blank
blank
HR
@Mail.ru
       © Электронная библиотека попечительского совета мехмата МГУ, 2004-2021
Электронная библиотека мехмата МГУ | Valid HTML 4.01! | Valid CSS! О проекте