Уважаемые коллеги, доброго времени суток! Представляем вам швейцарское научное издание Computational Complexity. Журнал имеет первый квартиль, издаётся в Birkhauser Verlag Basel, его SJR за 2021 г. равен 1,788, пятилетний импакт-фактор 1,149, печатный ISSN - 1016-3328, электронный - 1420-8954, предметные области - Вычислительная математика, Теоретические компьютерные науки, Общая математика, Теория расчетов и вычислений. Вот так выглядит обложка:
Редактором является Петер Бюргиссер, контактные данные - pbuerg@math.tu-berlin.de, oded.goldreich@weizmann.ac.il, dieter@cs.wisc.edu.
Дополнительные публикационные контакты - Albert.Singh@springer.com, journalpermissions@springernature.com, jan.holland@springer.com.
Вычислительная математика представляет собой выдающееся исследование в области вычислительной сложности. Предмет находится на стыке математики и теоретической информатики, с четким математическим профилем и строго математическим форматом. Центральными темами являются:
- модели вычислений;
- границы сложности (с особым акцентом на нижние границы);
- классы сложности;
- результаты компромиссов для последовательных и параллельных вычислений для "общих" (булевых) и "структурированных" вычислений (например деревья решений, арифметические схемы) для детерминированных, вероятностных и недетерминированных вычислений в наихудшем и среднем случаях.
Конкретные области включают:
- Структуру классов сложности (сокращения, вопросы релятивизации, степени, дерандомизация);
- Алгебраическая сложность (билинейная сложность, вычисления для многочленов, групп, алгебр и представлений);
- Интерактивные доказательства, генерация псевдослучайных чисел и проблемы сложности извлечения случайности в теории обучения криптографии;
- Логика теории чисел (сложность логических теорий, стоимость процедур принятия решений);
- Комбинаторная оптимизация и тестирование свойств распределенных вычислений приближенных решений.
Адрес издания - https://www.springer.com/journal/37
Пример статьи, название - Quantum generalizations of the polynomial hierarchy with applications to QMA(2). Заголовок (Abstract) - The polynomial-time hierarchy (PH) has proven to be a powerful tool for providing separations in computational complexity theory (modulo standard conjectures such as PH do not collapse). Here, we study whether two quantum generalizations of PH can similarly prove separations in the quantum setting. The first generalization, QCPHQCPH, uses classical proofs, and the second, QPHQPH, uses quantum proofs. For the former, we show quantum variants of the Karp-Lipton theorem and Toda's theorem. For the latter, we place its third level, QΣ3QΣ3, into NEXP using the ellipsoid method for efficiently solving semidefinite programs. These results yield two implications for QMA(2)QMA(2), the variant of Quantum Merlin-Arthur (QMAQMA) with two unentangled proofs, a complexity class whose characterization has proven difficult. First, if QCPH=QPHQCPH=QPH (i.e., alternating quantifiers are sufficiently powerful so as to make classical and quantum proofs ``equivalent''), then QMA(2) is in the counting hierarchy (specifically, in PoppppPopppp). Second, because QMA(2)⊆QΣ3QMA(2)⊆QΣ3, QMA(2)QMA(2) is strictly contained in NEXP unless QMA(2)=QΣ3QMA(2)=QΣ3 (i.e., alternating quantifiers do not help in the presence of ``unentanglement''). Keywords: Complexity theory; Quantum computing; Polynomial hierarchy; QMA(2); Semidefinite programming; Toda’s theorem