Уважаемые коллеги, доброго времени суток! Представляем вам швейцарское научное издание Computational Complexity. Журнал имеет первый квартиль, издается в Birkhauser Verlag Basel, его SJR за 2020 г. равен 0,973, пятилетний импакт-фактор - 1,082, печатный ISSN - 1016-3328, электронный - 1420-8954, предметные области - Теория расчетов и вычислений, Теоретические компьютерные науки, Вычислительная математика, Общие вопросы математики. Вот так выглядит обложка:
Редактором является Петер Бюргессер, контактные данные - pbuerg@math.tu-berlin.de.
Дополнительные публикационные контакты - oded.goldreich@weizmann.ac.il, dieter@cs.wisc.edu, Albert.Singh@springer.com, jan.holland@springer.com.
Журнал представляет выдающиеся исследования в области вычислительной сложности. Данный предмет находится на стыке математики и теоретической информатики, с четким математическим профилем и строго математическим форматом. Центральными темами являются: модели вычислений, границы сложности (с особым акцентом на нижние границы), классы сложности, результаты компромисса для последовательных и параллельных вычислений для "общих" (логических) и "структурированных" вычислений (например деревья решений, арифметические схемы) для детерминированных, вероятностных и недетерминированных вычислений, наихудший случай и средний случай Конкретные области концентрации включают:
- Структуру классов сложности (сокращения, вопросы релятивизации, степени, дерандомизация);
- Алгебраическая сложность (билинейная сложность, вычисления для многочленов, групп, алгебр и представлений);
- Интерактивные доказательства, генерация псевдослучайных чисел и извлечение случайности;
- Проблемы сложности в теории обучения критографии логика теории чисел (сложность логических теорий, стоимость процедур принятия решений);
- Комбинаторная оптимизация и приближенные решения тестирование свойств распределенных вычислений.
Адрес издания - https://www.springer.com/journal/37
Пример статьи, название - Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity. Заголовок (Abstract) - We investigate the power of randomness in two-party communication complexity. In particular, we study the model where the parties can make a constant number of queries to a function that has an efficient one-sided-error randomized protocol. The complexity classes defined by this model comprise the Randomized Boolean Hierarchy, which is analogous to the Boolean Hierarchy but defined with one-sidederror randomness instead of nondeterminism. Our techniques connect the Nondeterministic and Randomized Boolean Hierarchies, and we provide a complete picture of the relationships among complexity classes within and across these two hierarchies. In particular, we prove that the Randomized Boolean Hierarchy does not collapse, and we prove a query-to-communication lifting theorem for all levels of the Nondeterministic Boolean Hierarchy and use it to resolve an open problem stated in the paper by Halstenberg and Reischuk (CCC 1988) which initiated the study of this hierarchy. Keywords: Boolean hierarchies;
Lifting theorems; Query complexity
