Немного предыстории: Я заинтересован в поиске «менее известных» нижних границ (или результатов твердости) для задачи «Обучение с ошибками» (LWE) и их обобщений, таких как «Обучение с ошибками над кольцами». Для конкретных определений и т. Д., Вот хороший обзор Регева:...
Очень интересной открытой проблемой при изучении мер сложности булевой функции является так называемая гипотеза чувствительности и блочной чувствительности. Информацию о восприимчивости и чувствительности блоков вы можете найти в следующем посте С. Ааронсона по адресу...
Знается ли / изучена ли эта совершенная информационная игра на графиках? Учитывая график , два игрока поочередно выбирают ребро или изолированный узел. Если игрок выбирает ребро два узла и удаляются вместе с их падающими ребрами. Если игрок выбирает изолированный узел, узел удаляется. Первый игрок,...
Я пытаюсь понять протокол биткойнов в контексте компьютерной криптографической безопасности. Вопрос является справочным запросом к основам криптографических статей о биткойнах. Мой первый вопрос: какой абстрактный криптографический протокол пытается реализовать биткойн? Есть ли у нас определение...
Часть трудностей, связанных с поиском дополнительной информации об этой проблеме, заключается в том, что проблема сопоставления графов отличается от ее гораздо более известного кузена, проблемы сопоставления, но ее трудно отличить от нее при использовании поисковых систем. Даны два графа и такие,...
К настоящему времени имеется множество результатов по разделителям в графах, от плоского разделителя, разделителя деревьев, ограниченных графов ширины дерева, ограниченного рода родов и т. Д., И т. Д., И т. Д., И т. Д. Есть ли какой-нибудь хороший обновленный обзор по этому поводу и их...
Я заинтересован в изучении полных задач Изоморфизма графов (GI). В работе Kellogg S. Booth (1979) «Проблемы, полиномиально эквивалентные изоморфизму графа» доказано, что многие базовые задачи являются GI-полными с использованием методов замены краев, методов композиции и т. Д. Я хотел бы изучить...
Я читаю знаменитую статью Impagliazzo и Wigderson в 1997 году. Так как я новичок в этой области, и эта статья является краткой версией конференции, мне трудно следить за их доказательствами. В частности, некоторые из их новых теорем не имеют доказательств. Насколько мне известно, не было...
Я ищу ресурсы (желательно справочник) по сложным темам в алгоритмах (темам, выходящим за рамки учебников по алгоритмам, таким как CLRS и DPV). Тип материала, который можно использовать для преподавания таких тем в курсе алгоритмов, как курс Эрика Демейна и Дэвида Каргера « Расширенные алгоритмы» ....
Знаете ли вы задачи, которые являются W [1] -твердыми даже для ограниченных графов степеней? Метрическое измерение сложно на графах со степенью не более 3, но это W [2] -твердый. Красно-синий неблокатор был W [1] -твердым на ограниченных графах степеней, но в доказательстве была ошибка (книга...
Известно ли следующее утверждение? Утверждение : для любого графа с вершинами существует раскраска такая, что каждое независимое множество окрашивается не более чем цветами.n G O ( √граммGGNnnграммGGO (...
В теоремах бесплатно! Вадлер говорит, что характеристика параметричности может быть выражена в терминах слабых естественных преобразований, и это будет предметом дальнейшей статьи. На какую бумагу он ссылается? Я знаю, что категорический подход к параметричности использует динатуральные...
Обозначим через минимальную степень выхода в G , а через δ - ( G ) минимальную степень.δ+(G)δ+(G)\delta^+(G)GGGδ−(G)δ−(G)\delta^-(G) В связанном вопросе я упомянул расширение Гуила-Хури теоремы Дирака о гамильтоновых циклах , которое предполагает, что если тогда G...
Рассмотрим граф (задача имеет смысл как для ориентированных, так и для неориентированных графов). Назовите матрицей расстояний : - это кратчайшее расстояние от вершины до вершины в для некоторой фиксированной функции агрегирования (например, или ).GGGMGMGM_GGGGMG[i,j]MG[i,j]M_G[i,...
У Конвея очень приятная конструкция из сюрреалистических чисел. Это «числа», которые содержат как действительные числа, так и порядковые числа, полностью упорядочены и имеют все свойства поля (за исключением того, что они образуют не множество, а класс). Смотрите, например, этот PDF или Википедию...
Рассмотрим следующую проблему: Для двух строк x, y решите, существует ли строковый гомоморфизм f такой, что f (x) = y. Легко показать , что эта проблема находится в . Есть ли что-то еще, что мы можем сказать об этой проблеме? Например, это в c o N P или даже в P ?NPNPNPcoNPcoNPcoNPPPP Эта проблема...
Как мы знаем, определение вычислительной сложности алгоритма практически не вызывает противоречий, но определение вычислительной сложности вещественных чисел или моделей вычислений над действительными значениями не в таком случае. Мы знаем модель и модель Блюма и Смалеса в книге «Вычислительный...
Я хотел бы знать ( в связи с этим другой вопрос ) , если нижние оценки были известны следующие задачи тестирования: один получает доступ запроса к последовательности неотрицательных чисел п ≥ ⋯ ≥ 1 и & epsi ; ∈ ( 0 , 1 ) с обещанием, что либо k n k = 1 a k = 1, либо ∑ n k = 1 a k ≤ 1 - ε .aN≥ ⋯...
Я аспирант в области теоретических компьютерных наук, и в частности, алгоритмы аппроксимации. Теперь я нахожу, что меня больше интересует чистая математика (я могу сказать это, потому что мне, кажется, нравятся курсы математики больше, чем курсы CS). Я хотел бы спросить, есть ли области...
Есть алгоритмическая теория графов / теория чисел / комбинаторика / теория информации / теория игр. Есть ли алгоритмический математический анализ? Согласно вики, математический анализ включает в себя теории дифференцирования, интегрирования, измерения, пределов, бесконечных рядов и аналитических...