All Questions

Filter by
Sorted by
Tagged with
0 votes
0 answers
27 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 ...
user avatar
-1 votes
0 answers
47 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=\{...
user avatar
  • 12.5k
0 votes
1 answer
39 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 ...
user avatar
4 votes
1 answer
61 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" ...
user avatar
  • 41
1 vote
1 answer
47 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 ...
user avatar
  • 45
1 vote
0 answers
44 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 ...
user avatar
1 vote
0 answers
72 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 ...
user avatar
  • 111
5 votes
0 answers
54 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 $\...
user avatar
  • 1,112
-2 votes
0 answers
53 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 ...
user avatar
0 votes
0 answers
33 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 $\...
user avatar
1 vote
0 answers
42 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 ...
user avatar
-1 votes
0 answers
41 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 ...
user avatar
0 votes
1 answer
65 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=...
user avatar
  • 57
-1 votes
0 answers
17 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 ...
user avatar
0 votes
0 answers
41 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 ...
user avatar
3 votes
0 answers
61 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 ....
user avatar
  • 133
-1 votes
0 answers
57 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 ...
user avatar
  • 1
1 vote
0 answers
52 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 ...
user avatar
3 votes
1 answer
134 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 ...
user avatar
  • 33
6 votes
1 answer
120 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-...
user avatar
  • 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??
user avatar
0 votes
0 answers
52 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 ...
user avatar
-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 ) ...
user avatar
0 votes
0 answers
76 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|...
user avatar
  • 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 ...
user avatar
0 votes
0 answers
57 views
+50

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'$ ...
user avatar
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 ...
user avatar
  • 81
4 votes
0 answers
64 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)...
user avatar
  • 41
2 votes
0 answers
74 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$-...
user avatar
1 vote
1 answer
43 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 ...
user avatar
0 votes
0 answers
44 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
-3 votes
0 answers
133 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 ...
user avatar
0 votes
0 answers
65 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}...
user avatar
6 votes
0 answers
118 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 ...
user avatar
  • 5,933
0 votes
0 answers
42 views

Does for every k $\Sigma _k exists Sigma_k complete issue [closed]

My question is: Does every Sigma_k has a Sigma_k complete problem?
user avatar
1 vote
0 answers
104 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 ...
user avatar
-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 ...
user avatar
  • 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 ...
user avatar
1 vote
1 answer
213 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 (...
user avatar
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 ...
user avatar
  • 133
2 votes
0 answers
48 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 ...
user avatar
2 votes
1 answer
125 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$-...
user avatar
1 vote
0 answers
53 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 ...
user avatar
  • 387
-5 votes
0 answers
46 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 ...
user avatar
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$ ...
user avatar
-1 votes
0 answers
39 views

What is the bit complexity for Unitary Matrix multiplication?

In quantum computing, operation by 2 subsequent gates counts as O(1) step, however, if we have to simulate the same operation using a classical computer, we will need to multiply 2 unitary matrices. ...
user avatar
4 votes
1 answer
201 views

Does double majoring with math in undergrad help one grasp TCS topics more easier?

I'm a CS major. However, a lot of TCS topics seem to be in the realm of pure math. Should I add a math major to complement understanding and for a future career in TCS?
user avatar
2 votes
0 answers
84 views

Natural proofs and size of propositional formulas

Given a formula $\phi$ of propositional logic, we define its size $|\phi|$ as the number of proposition symbols that $\phi$ contains (counted with multiplicity). For example, $|(p \land p)| = 2$. Let $...
user avatar

15 30 50 per page
1
2 3 4 5
238