All Questions
11,858
questions
0
votes
1
answer
22
views
What set of sequential 2-bit inputs would it take for any system with 2 bits of memory to not be able to no it is not being tested
In a computer game, a player is tasked with making a sequential circuit that takes two one-bit inputs (for a total of four combinations) and outputs a bit depending on both the current input and the ...
- 101
2
votes
1
answer
175
views
Similarities and differences between Pie and popular languages with dependent types
The book The Little Typer explains dependent types using a toy language called Pie (https://github.com/the-little-typer/pie).
How similar is Pie to the popular languages with dependent types: Coq, ...
- 123
2
votes
0
answers
44
views
Ignore side effect in monadic code
Is there a standardized notion of something that removes side effects for an element in a monad?
In the case of state monad:
An element mx : m X is effectively <...
- 151
3
votes
2
answers
79
views
How exactly does a compatible reduction relation change the $\pi$-calculus?
The reduction relation given for the $\pi$-caculus is usually not compatible (i.e., it's not preserved under arbitrary contexts). Quoting Milner's The Polyadic $\pi$-Calculus: A Tutorial:
It is ...
- 283
-4
votes
0
answers
56
views
What data structure for O(1) lookup of multiple keys per value?
I know hash collisions are bad, but are there any hash tables purposefully designed to allow multiples keys per value? Sometimes I want to store something for O(1) lookup where it also has another ...
- 93
-1
votes
0
answers
102
views
Relation between BSS and Turing models
$P_\mathbb R$ is the set of languages decidable in polynomial time over the real $BSS$ machine defined in https://en.wikipedia.org/wiki/Blum%E2%80%93Shub%E2%80%93Smale_machine.
Let $0-1-P_\mathbb R=\{...
- 12.5k
0
votes
1
answer
55
views
Is there FPT or XP algorithms knowm for Shortest Steiner cycle and $(a,b)$-Steiner path problem
Shortest Steiner cycle and $(a,b)$-Steiner path problem are generalizations of optimization versions of Hamiltonian cycle and Hamiltonian path problems.
The Shortest Steiner cycle problem is defined ...
- 141
4
votes
1
answer
88
views
"Operations" in category theory that are not defined for arrows
Functors in category theory are defined for both objects and arrows. Depending on how they treat arrows, functors are characterized as either covariant or contravariant. Some "operations" ...
- 41
2
votes
1
answer
62
views
Question about algorithm for enumerating minimal AB-separators
Let $A,B\subseteq V(G)$ be two non-adjacent, disjoint subsets of vertices in $G$.
A subset $S\subseteq V(G)\setminus (A\cup B)$ is an $AB$-separator if the graph $G[V\setminus S]$ contains two ...
- 55
1
vote
0
answers
56
views
Can we describe any context-sensitive language by a grammar without left recursion?
The main question: is it possible to avoid left recursion in a context-sensitive grammar (see example below), i.e., if for any context-sensitive language $L$, there exists some context-sensitive ...
- 11
1
vote
0
answers
82
views
Are there more learnable but undecidable cases except the halting problem
Per request, I cross post the question here which is original from math.stackexchange
In the ICML 1996 paper, On the Learnability of the Uncomputables, by Richard Lathrop, he proved that halting ...
- 111
5
votes
0
answers
65
views
Relationship between natural deduction refutation and tableaux for propositional logic
Which kind of relationship is there between natural deduction refutations of a set f propositional logic assumptions, and the corresponding tableaux?
For example, consider the unsatisfiable set $\...
- 1,112
-2
votes
0
answers
60
views
Models of computation and cardinality [closed]
In university, I was taught the computational model hierarchy given in the following figure: https://devopedia.org/images/article/210/7090.1571152901.jpg
Essentialy, Pushdown Automata (PA) can solve ...
- 1
0
votes
0
answers
36
views
If two functions are close apart can I prove the difference of their empirical loss is also small?
I am trying to understand the proof of Theorem 3 in the paper "A Universal Law of Robustness via isoperimetry" by Bubeck and Sellke.
Basically there exist atleast one $w_{L,e}$ in $\...
- 113
1
vote
0
answers
45
views
Is there an FPT or XP algorithm known for this version of $k$-edge disjoint paths problem?
The shortest $k$-edge disjoint paths problem is defined as follows:
Input: An undirected graph $G=(V,E)$ and $k$ pairs of vertices $(s_1,t_1),\ldots,(s_k,t_k)$.
Question: Find (if exist) $k$-pairwise ...
- 141
-1
votes
0
answers
44
views
Contradiction via the Hierarchy Theorem [closed]
I am new to Complexity theory, there is a small amount of it in a masters module I am taking. They introduced the Hierarchy Theorem without a rigorous proof.
This is the statement of theorem I was ...
0
votes
1
answer
81
views
The Complexity of Multi-Objective Optimization
Given a vector set $V=\{v_i\}_{i=1}^n$ with $n$ vectors where $v_i\in \mathbb{R}^d$ is a vector and a transfer matrix $\mathbf{W}\in \mathbb{R}^{d_1\times d}$, the target is to select two subsets $V_1=...
- 57
-1
votes
0
answers
18
views
Determine number of possible formal languages with a nerode-index of k (k number of equivalence classes)
How can one determine the number of possible formal languages with nerode index of k? For example: How many formal languages are there with a nerode-index of 2?
At first i tried to draw the ...
- 99
0
votes
0
answers
44
views
Solving sampling problems with circuits?
If I allow a circuit family (say, poly size, polylog depth) poly($n$) bits of randomized advice, then I can ask if its output samples from certain distributions or not. However I don't know what the ...
- 21
3
votes
0
answers
63
views
Is there a standard way to "point" at subterms in a lambda expression?
Let's say I have a lambda expression
$$ (\lambda x . (\lambda w.ww)x) y $$
There are a bunch of subterms:
$(\lambda x . (\lambda w.ww)x) y$
$\lambda x . (\lambda w.ww)x$
$(\lambda w.ww)x$
$\lambda w ....
- 133
-1
votes
0
answers
60
views
How to prove a problem does not have an approximation algorithm?
Is it possible to prove that a certain problem does not have an approximation algorithm?
Like perhaps show that it is not in APX.
Is there a formal way to do it? Perhaps reduce it from a problem that ...
- 1
1
vote
0
answers
53
views
Cheapest Insertion is $2$-approximation for TSP
Consider the Cheapest Insertion Algorithm on a complete graph with $n$ vertices, where each edge $uv$ has a weight $w(uv)$, and the weights satisfy the triangle inequality $w(xz)\leq w(xy)+w(yz)$ for ...
- 11
3
votes
1
answer
138
views
Sample complexity lower bound to learn the mode (the value with the highest probability) of a distribution with finite support
Say we have a black-box access to a distribution $\mathcal{D}$ with finite support $\{1,2,...,n\}$ with probability mass function $i \mapsto p_i$. How many samples of $\mathcal{D}$ are needed to learn ...
- 33
6
votes
1
answer
125
views
What are the application of Scott-Topology in theoretical computer science?
During a work I came across the Scott-Topology and I see that Scott-continuous functions show up in the study of models for lambda calculi. What I cannot understand is how this enrich the lambda-...
- 69
-4
votes
1
answer
47
views
I have to make a dfa over the alphabet Σ = { 0, 1, 2 } of strings that end with the same digit twice; e.g., strings that end in 00, 11, 22
hi can you please go over my dfa for this and tell me if its correct??
- 1
0
votes
0
answers
54
views
Short UNSAT Certificates for X3SAT
Exactly 1 in 3 SAT ($X3SAT$) is a variation of the Boolean Satisfiability problem. Given an instance of clauses where each clause has three literals, is there a set of literals such that each clause ...
- 499
-4
votes
0
answers
20
views
How can I calculate the computational complexity of an equation composed of 2n multiplications and 2nm^2 additions? [closed]
I want to calculate the computational complexity in term of the big (O).
My equation is:
It composed of 2n multiplications and 2nm^2 additions.
The complexity of this equation is it O( 2n + 2nm^2 ) ...
- 93
0
votes
0
answers
80
views
Complexity of the distance between the average vector of two subsets
Given a vector set $V=\{v_i\}_{i=1}^n$ with $n$ vectors, where $v_i\in \mathbb{R}^d$ is a vector, the target is to select two subsets $V_1=\{v_j\}_{j=1}^{|V_1|} \subset V$ and $V_2=\{v_k\}_{k=1}^{|V_2|...
- 57
-4
votes
0
answers
30
views
Solving K-Flip SAT problem in Polynomial time
Given a dataset with N variables, M clauses in CNF form, and a randomly generated truth assignment T. I am trying to find a truth assignment T' that flips at most k variables and satisfies more ...
- 1
0
votes
0
answers
60
views
Direct fpt reduction from Weighted 3SAT to Weighted 2SAT
In parameterized complexity, for each fixed $q$, the problem Weighted $q$-CNF SAT is W[1]-complete. In particular, this means that one can turn a 3CNF formula $\varphi$ into a 2CNF formula $\varphi'$ ...
- 419
8
votes
1
answer
1k
views
Are there survey papers in theoretical computer science?
Are there conferences or journals where we can publish surveys/literature review papers related to theoretical computer science problems? If provide a list of such conferences and journals.
I know ...
- 83
4
votes
0
answers
68
views
Are there classes for that FO-model checking is FPT on hypergraphs?
For graphs, there are many classes that admit FPT-algorithms for model checking of first order logic, e.g. the class of nowhere dense graphs by Grohe et. al.
Are there similar results for ($k$-uniform)...
- 41
2
votes
0
answers
76
views
Reference for complete problems for $FNP^{NP}$
I'm looking for a reference for complete problems for $FNP^{NP}$, i.e., the class of functional problems solvable
by a polynomial time non-deterministic Turing machine that has access to an $NP$-...
- 736
1
vote
1
answer
44
views
CFG - How can I describe a language that dictates a word and its opposite?
I have this question from my Automata class and I am unsure if there's a way to do this.
Assuming u,v ∈ {0,1}* and at every character in the word u, the character at the same position in the word v is ...
0
votes
0
answers
45
views
Did anyone ever adapted TCS data structure results (e.g. vEB trees) into Governance structures?
Did anyone ever adapted TCS data structure results (e.g. vEB trees) into Governance structures?
Many of the structures underlying current societies and their governance were designed more than 100 ...
- 2,391
0
votes
0
answers
33
views
Defining a process without internal events
I'm currently working through the book The Prinicples of Protocol Design by Robin Sharp where the reader is introduced to the theory of Communicating Sequential Processes (CSP).
The first example ...
- 1
0
votes
0
answers
42
views
Perfect simulation of classical dynamical systems
In his paper https://royalsocietypublishing.org/doi/10.1098/rspa.1985.0070, David Deutsch defines the perfect simulation of a system S by a computing machine M if there is a program for M that makes M ...
-3
votes
0
answers
134
views
For VCP and fixed value k, what's the result if we prove optimal value > (n/2)+(n/k) or we can produce a feasible objective value < (kn)/(k+1)?
I wrote a new idea (by a combination of a well-known SDP formulation and a randomized procedure to conclude that for the Vertex Cover Problem the optimal value > (n/2)+(n/k) or we can produce a ...
0
votes
0
answers
66
views
Simplify or bound using Big-O notation
I was following a research paper which have the following equation:
$\left(1-\frac{1}{K}\right)^{K-i}\left[1-\left(1-\frac{1-p}{K}\right)^{i}\right]=\frac{i(1-p)}{K}+O\left(\left(\frac{i}{K}\right)^{2}...
- 99
7
votes
0
answers
120
views
Computing permanents when we are promised that the value of the permanent is large
Suppose you are given an $n$ by $m$ real matrix (or even complex matrix) with orthonormal rows. ($m=poly(n)$, say $m=n^2$.) For an $n$-tuples of columns (with repetitions) from M we consider the ...
- 5,943
1
vote
0
answers
105
views
proof that 2-SAT is P-hard [closed]
i'm doing university work about the 2-sat problem and it is asked why 2-sat is p-hard. We discussed that 3-sat is np-hard and proved this by reduction from cnf-sat to 3cnf-sat. for my work the ...
- 11
-2
votes
0
answers
14
views
relevance of a large prime number in polynomial rolling hash function
polynomial rolling hash is one the ways to represent a string as integer uniquely. The algorithm mentioned here uses a large prime number
verbatim from the article
...
- 1
0
votes
0
answers
19
views
Round Robin Algorithm ( Process scheduling)
Good morning everyone
I'm facing a problem with the RR Algorithm. Here's the question :
draw the Gantt diagram for quantum=1 and quantum=4 for
this processes
this is the professor's answer:
quantum=1 ...
1
vote
1
answer
217
views
Are there 'poision-pill' research questions in TCS?
I intend to double major in CS/Math and go to grad school for TCS. I have some - unorthodox - research ideas I would like to pursue for grad school. At the very least, they are interdisciplinary (...
- 307
0
votes
1
answer
68
views
Can you always throw away the types when evaluating lambda expressions?
As I understand it, in the simply typed lambda calculus you can type-check your terms, then throw away all the types and do the evaluation exactly as if it was the untyped lambda calculus. Is that ...
- 133
2
votes
0
answers
50
views
Pebble games and conversions to bounded width circuits
Questions: Are there references which mention the relation between pebble games and conversions to bounded width circuits?
Here, "conversions to bounded width circuits" means that circuits ...
- 689
2
votes
1
answer
126
views
Complexity of the Complete (3,2) SAT problem?
A complete $k$-CNF formula is a $k$-CNF formula which contains all clauses of size $k$ or lower it implies.
Deciding the satisfiability of a $k$-CNF formula is clearly a tractable problem since a $k$-...
- 1,069
1
vote
0
answers
54
views
Code indistinguishability assumption for Code based cryptography (in special cases)
Cryptosystems that are based on error correcting codes are often based with hardness of the two problem.
Computational syndrome decoding is hard
Indistinguishability Assumption (IA): Distinguishing ...
- 387
-5
votes
0
answers
47
views
Can all Combinatorial Optimization (or NP Optimization problems) be (theoretically) solved with A*?
I am trying to formulate any NP Optimization (or Combinatorial Optimization) problem as a generic search problem that can be solved with the shortest pathfinding algorithms like BFS, DFS, A*, etc.
Is ...
0
votes
0
answers
87
views
Separation oracle for breaking cycles in directed graph
I am working on a directed graph problem and am collaterally interested to know whether there is a separation oracle for the following set of linear constraints.
We are given a directed graph $G$ ...
- 89