All Questions

Filter by
Sorted by
Tagged with
0 votes
0 answers
70 views

Minimize the dominating points

Given a set of n points in 3d space and an integer k, it is NP-hard to select k points from the skyline to maximize the number of points dominated by them. Is it still NP-hard to select k points form ...
tics's user avatar
  • 1
0 votes
1 answer
121 views

Is the protocol perfect zero knowledge?

Consider such protocol for $GI$ (Graph-isomorphism problem). $P$ randomly chooses permutations $\sigma_1, \sigma_2, ..., \sigma_k$ and sends $H_1 = \sigma_1(G_0), ..., H_k = \sigma_n(G_0)\ (k > 1)$;...
GeoArt's user avatar
  • 9
0 votes
0 answers
17 views

Natural reduction from partially observable Markov decision process planning to reconfiguration

Suppose I want to prove the PSPACE-completeness of reconfiguration by reducing partially observable Markov decision process (POMDP) planning to it. Is there a known natural / succinct reduction from ...
delete000's user avatar
  • 828
9 votes
1 answer
215 views

algebraic topology in distributed computing

I have just discovered the paper of M. Herlihy and N. Shavit on the use of algebraic topology methods in TCS and distributed computing in particular. Now I am wondering if there is any further work ...
timtombobjohn's user avatar
0 votes
0 answers
54 views

Non-linearly ordered hierarchy of classes between NP and NEXP

I'm interested in the hierarchy of complexity classes between NP and NEXP. I have asked before about this Hierarchy of classes between NP and NEXP and found that already the time hierarchy theorems ...
user1868607's user avatar
  • 1,049
7 votes
2 answers
384 views

Problems where "maximal" is hard, but "maximum" is easy?

For a lot of problems, it's easy to find a maximal solution (say, with a greedy algorithm), but that will in general not be maximum, and in fact computing a maximum solution might be computationally ...
Federico Lebrón's user avatar
4 votes
1 answer
142 views

Does Rush-Hour (or Klotski) admit a search-to-decision reduction?

Consider puzzles like Rush-Hour or Klotski. When suitably generalized, such puzzles are known to be PSPACE-complete, but surely there is an interesting subclass of instances intesecting NP (and not ...
Mark S's user avatar
  • 1,125
4 votes
1 answer
129 views

Constructing vector valued boolean circuits from boolean circuits

This is a reference request. I'm interested in the compositional construction of small boolean circuits for vector-valued boolean functions $\phi : \mathbb{B}^m \rightarrow \mathbb{B}^n$ for $n >...
Martin Berger's user avatar
1 vote
0 answers
61 views

Is this kind of "multi-reduction" interesting?

Given a decision problem $P$, the usual way to show that it is NP-hard is to find a known NP-hard problem $Q$, and show a polynomial-time algorithm that transforms every instance $I_Q$ of $Q$ to an ...
Erel Segal-Halevi's user avatar
2 votes
0 answers
109 views

Searching for a proof that non-deterministic logspace with errors is contained in $PL$

In this 10 year old question Non-deterministic logspace with two-sided error the author asked for a complexity class related to $NL$. Namely $NL$ but we are allowed to have two-sided error for the ...
tcs_enjoyer's user avatar
2 votes
1 answer
91 views

planar circuit logspace completeness

In https://dl.acm.org/doi/pdf/10.1145/1008354.1008356, a proof is given for PCV is log space complete. I do not understand the construction though, a circuit is given but it is not clear to me what is ...
redrobinyum's user avatar
5 votes
2 answers
201 views

The empty tree-word for regular tree languages

Are there references that consider the "empty tree-word" as an allowable element of regular languages of trees? Are there situations where it is more sensible to allow an empty tree-word? ...
TomKern's user avatar
  • 489
8 votes
1 answer
163 views

Primitive recursive permutations

How to show that the inverse of a primitive recursive permutation of $\mathbb{N}$ is not necessarily a primitive recursive function?
ijon's user avatar
  • 115
4 votes
1 answer
77 views

Reference request: finite field computation over the Word-RAM model

Let $q = p^\ell$ be a positive integer power of a prime $p$, of size $q = \text{poly}(n)$. Over the Word-RAM model (with words of size $O(\log n)$), how quickly can we perform addition and ...
Naysh's user avatar
  • 686
5 votes
1 answer
683 views

PCP without reading the statement

The PCP theorem (very imprecisely!) states that for every $x\in L\in NP$ there is a polynomial witness $w$ such that for some random algorithm it is enough to read a constant number of bits of $w$ to ...
domotorp's user avatar
  • 14k
6 votes
1 answer
284 views

How stringent is the peer review process of ECCC exactly?

Apologies for the soft question. ECCC (the Electronic Colloquium on Computational Complexity), on its website (ECCC), says it is a compromise between the negligible peer review of ArXiv and the long ...
Tejas's user avatar
  • 369
3 votes
0 answers
47 views

Cuthill - Mckee Guarantees?

I'm interested in the following problem: given $M$, a $p \times p $ symmetric sparse matrix (the number of non-zero elements in each row is at most $s \ll p$), find a matrix $B = PMP^T$ where $P$ is a ...
WeakLearner's user avatar
2 votes
1 answer
95 views

The true meaning of sampling from a distribution in the context of active learning

I would like to understand intuitively what it means to sample from a distribution $\mathcal{D}$. It may sound like a dumb question, but I can't find an answer anywhere, a colleague recommended ...
Guesttilunderstandingnature's user avatar
4 votes
0 answers
43 views

Relationship between differential lambda calculus and automatic differentiation

I'm familiar with both, especially the dual numbers form of automatic differentiation. I'm wondering if someone could clarify the relationship between the two -- as I understand it, they coincide on ...
Student's user avatar
  • 41
6 votes
0 answers
65 views

Böhm tree with pairs (product types)

I am looking for references for a notion of Böhm tree for the λ-calculus with pairs and projections (and the reduction rule $\pi_i\, \langle t_1, t_2\rangle \longrightarrow t_i$). I'm only aware of ...
Lê Thành Dũng 'Tito' Nguyễn's user avatar
5 votes
1 answer
183 views

What is the probability a random language in $\mathsf{PSPACE}$ is in $\mathsf{P}$?

Suppose I am drawing a venn diagram of complexity classes, and I don't want one that is the most visually pleasing, but the most accurate. How much of PSPACE should P take up? Let $L$ be chosen ...
abrahimladha's user avatar
0 votes
0 answers
50 views

How to implement the Regev's factoring algorithm on Qiskit?

I want to use the Regev algorithm to factorize 77 and demonstrate the principles of the algorithm. However, I am unsure how to construct the specific circuit. Additionally, why does the algorithm ...
REESE XIE's user avatar
0 votes
0 answers
61 views

Resolution lower bound for pigeonhole principle when placement clauses are shortened

Consider the standard CNF encoding of pigeonhole principle $PHP_{n}^{n+1}$: $$ \text{Placement clauses: } x_{i,1} \lor x_{i,2} \lor \cdots \lor x_{i,n} \forall i \in [n+1] $$ $$ \text{Collision ...
aba's user avatar
  • 91
1 vote
0 answers
91 views

Non-convex optimization with correlated minima

I am thinking of non-convex optimization problems where the minima are somehow correlated. Maybe there are symmetry relationships among minima or maybe there is regularity in spacing among minima in ...
Omar Shehab's user avatar
1 vote
1 answer
99 views

Equivalence of regex in Programming language theory

I'm studying about the regular expression, but I'm a little confused about the concept of 'equivalence'. When I want to check "[[r]] ≡ [[ε]]", it's false if r is NULL, true if epsilon, false ...
Kleenex's user avatar
  • 13
0 votes
0 answers
66 views

On $PP$ vs $\oplus P$ in CC

In communication complexity is it known that the classes $PP^{cc}$ and $\oplus P^{cc}$ satisfy $PP^{cc}\not\subseteq\oplus P^{cc}$?
Turbo's user avatar
  • 13k
5 votes
1 answer
184 views

Does every computable function have infinitely many "non-padded" representations?

It's well-known that every computable function has infinitely many representations (when they're expressed via recursive functions, or programs, etc.). I'm trying to understand whether there are ...
Alex Altair's user avatar
-4 votes
1 answer
110 views

Can you find a counterexample / disprove my P=NP solution?

I've posted the full article here. The source code is available here. Basically, in the Linear Programming (LP) task, we solve a system of inequalities: one inequality per BSAT clause. In each ...
Serge Rogatch's user avatar
1 vote
0 answers
88 views

Planar Turing Machine with (relatively) Small Alphabet

There is a simple construction that takes any drawing of a Turing Machine in the plane and outputs another planar, equivalent one with a "small" blowup in the number of states, and only two ...
Ryan Dougherty's user avatar
0 votes
1 answer
130 views

Hierarchy of classes between NP and NEXP [closed]

Ladner's theorem shows that if $P$ is different from $NP$ then there are actually infinitely many complexity classes (for polynomial time reducibility) between the two. I was wondering if this is also ...
user1868607's user avatar
  • 1,049
7 votes
0 answers
109 views

Journals for expository papers in theoretical computer science?

Is there a suitable venue to publish compilations of old results in TCS? (More specifically, in my case, "logic in computer science", but I am also curious about answers concerning ...
Lê Thành Dũng 'Tito' Nguyễn's user avatar
1 vote
0 answers
83 views

Development details of the Hungarian algorithm for Maximum Perfect Bipartite Matching

There are two realization forms of Hungarian algorithm. One is the original dynamic matrix, and the other is via equality subgraph. I just checked the original paper of Hungarian method by Kuhn, which ...
Shawxing Kwok's user avatar
2 votes
1 answer
78 views

Time Complexity of KnuthBendixCompletion Algorithm [closed]

I am currently studying the Knuth-Bendix completion algorithm and trying to understand the factors that contribute to its time complexity. This algorithm is used to transform a set of rewrite rules ...
Navvye's user avatar
  • 21
0 votes
1 answer
137 views

Parity of the sum of pseudorandom bits over a non-sparse set of inputs

Suppose I have a pseudorandom function (in the theoretical sense) $X\colon\{0,1\}^{n+m}\rightarrow\{0,1\}$ (where $m$ is polynomial in $n$) and a non-empty set $S\subseteq\{0,1\}^m$ ($S$ is not sparse,...
Tejas's user avatar
  • 369
6 votes
0 answers
128 views

Is there a known correlation between the Strong Exponential Time Hypothesis (SETH) and the existence of one-way functions?

It is known that (one-way functions exist $\implies$ $\textbf{P}\neq \textbf{NP}$) and as far as my knowledge goes, the converse is not known to be true. Are there any known results correlating $\...
Tejas's user avatar
  • 369
2 votes
1 answer
103 views

A monad law about bind and function composition

This law about bind and function composition type checks: bind m (f o g) = f (bind m g) but it is not clear whether it is true and how can it be proved. How could ...
Gergely's user avatar
  • 123
2 votes
1 answer
107 views

Constrained Bipartite Matching

Let $G = (X,Y,E)$ be a bipartite graph. For some $A \subseteq X$ we say that $A$ can be perfectly matched if there is a matching $M \subseteq E$ such that all vertices in $A$ are matched; that is, for ...
John's user avatar
  • 412
5 votes
1 answer
255 views

What is the 'P=NP?' building?

I remember that I read somewhere some years ago that they've built a computing building with the 'P=NP?' question built in it from bricks so that they later have the option to rearrange these bricks ...
domotorp's user avatar
  • 14k
0 votes
1 answer
108 views

What is a model theory / category theory basis of System F-omega that corresponds to what programmers actually do?

In what books or papers is it explained how the type constructions of a functional programming language correspond to category theory, and what are the models (a rigorous semantics) of programs of ...
winitzki's user avatar
  • 542
6 votes
0 answers
135 views

Proof complexity of Sudoku

Let $P$ be a $N$x$N$ Sudoku puzzle (assume $N=n^2$ for some $n\in \mathbb{N}$, e.g. standard $9$x$9$ puzzle is $n=3$). We can represent it in propositional logic as follows: Variables $p_{i,j,k}$: ...
Kaveh's user avatar
  • 21.7k
3 votes
1 answer
89 views

Deciding if max-cut with negative edge weights has a solution with positive value

I am interested in the complexity of the decision problem whether max-cut with positive and negative edge weights has a solution with positive value: Given a graph $G=(V, E)$ and edge weights $w: E \...
badboul's user avatar
  • 77
1 vote
1 answer
93 views

Formalising Church numerals in Agda

Beginer here. I'm trying to show that the closed $\beta$-nf's of type $ (\iota \to \iota) \to (\iota \to \iota) $ are the Church numerals ($\iota$ the base type, using the simply-typed lambda calculus)...
lfrg's user avatar
  • 13
1 vote
1 answer
101 views

Turing 1936 Skeleton Tables Procedure

I am reading Turing 1936 to learn about the halting problem from its origin. However, I encountered a roadblock upon reaching section four, in which Turing demonstrates that his m-configuration tables ...
Missingno's user avatar
4 votes
1 answer
138 views

Intersection Non-Emptiness for Two-Way Finite Automata

We know that checking the emptiness of intersection of an unbounded number of deterministic finite automata is PSpace-complete, and that just the emptiness problem for a nondeterministic two-way ...
A. G.'s user avatar
  • 43
5 votes
3 answers
208 views

Why is order/choice an issue for a logic for PTIME

As I'm reading on the question of a logic for PTIME and in particular about CPT and its variants, whilst things make sense and I follow along, I came to realise that I don't fundamentally understand ...
Matei Chesa's user avatar
2 votes
0 answers
80 views

Im looking for papers to read to strengthen my understanding of overall cs theory

I took automata theory and the things we learn in that class interest me a lot and am looking to read more papers to take a deeper dive into cs theory if any of y'all have any paper suggestions that ...
Emre Guzelordu's user avatar
0 votes
1 answer
43 views

Can you fix integral LP variables for a non-integral polytope without affecting the existence of integral optima?

Suppose I have a linear program $LP1=\{\mbox{Maximize }c^\top x \mid x\in \mathcal{P}\}$ for some polytope $\mathcal{P}\subseteq [0,1]^n$, which is known to have fractional extreme points. Suppose ...
gov's user avatar
  • 341
0 votes
0 answers
38 views

Bipartite Matching with a Partition Constraint over the Vertices

Let $G = (X,Y,E)$ be a bipartite graph and let $X_1,\ldots,X_r$ be a partition of $X$. For some $i \in \{1,\ldots, r\}$ and $E' \subseteq E$ we say that constraint $X_i$ is covered by some $E'$ if ...
John's user avatar
  • 412
0 votes
0 answers
69 views

What work on min max connectivity problems has there been?

For instance has min max spanning/steiner/prize-collecting tree been studied. i.e. each edge $e$ has costs $c_{v,e}$ of each resource $i$. And we wish to find a spanning tree minimizing the maximum ...
Hao S's user avatar
  • 228
0 votes
1 answer
28 views

How can I optimize the assignment of object sets to workers with pre-existing caches to minimize discrepancy?

I am working on a problem where I have $n $ workers, each with a cache that already contains a specific set of objects. Additionally, I receive $n \times m$ sets of objects. My task is to assign ...
Han Tian's user avatar

15 30 50 per page