# All Questions

11,857 questions
Filter by
Sorted by
Tagged with
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 ...
47 views

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 ...
33 views

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 ...
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 ...
61 views

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 ...
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-complete. In particular, this means that one can turn a 3CNF formula $\varphi$ into a 2CNF formula $\varphi'$ ...
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 ...
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)...
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$-...
1 vote
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 ...
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 ...
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 ...
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 ...
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 ...
65 views

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}... 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 ... 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?
1 vote
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 ...
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 ...
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
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 (...
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 ...
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 ...
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$-...
1 vote
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 ...
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 ...
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$ ...
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. ...
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?
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 \$...