# All Questions

9,939 questions
64 views

### What is the competitive ratio of a $d$-way associative LRU cache?

In a caching problem, items arrive online, and the algorithm needs to decide which elements to keep in the cache. If the current item is not cached, we pay a penalty of $1$. It is well known that for ...
226 views

309 views

### Is the complement of { www | … } context-free?

It is well-known that the complement of $\{ ww \mid w\in \Sigma^*\}$ is context-free. But what about the complement of $\{ www \mid w\in \Sigma^*\}$?
218 views

### Size of complement of context-free language

Let $L$ be a context-free language, $\bar L$ be its complement and $\bar L_n$ be the length $n$ words in $\bar L_n$. What is known about $|\bar L_n|$? Note that it is known that $|L_n|$ is either ...
207 views

### NP-hard problems on the class of caterpillars

My question is whether there exist an NP-hard problem that has only a caterpillar as input. By saying only caterpillar as input, I wanted to emphasize that no function (eg: weights on vertices or ...
121 views

### Star seperators to explain computational complexity of algorithms on a class of graphs?

A lot of NP-hard optimization problems on graphs which are perfect become solvable in polynomial time. Unfortunately, the class of graphs that arise in my problem are not perfect. The graphs can be ...
422 views

108 views

### Minimum relevant variables in linear system - additive approximation

In the problem Minimum Relevant Variables in Linear System (Min-RVLS), the input is a linear system, e.g.: $$A x = b$$ and the goal is to find a solution $x$ with as few nonzero variables as ...
78 views

### Algorithm for K-best NON perfect bipartite matchings

I was reading this great article: https://core.ac.uk/download/pdf/82129717.pdf It solves a generalization of the maximum sum assignment problem by finding the k best assignments and not only the best....
142 views

### Immutable Space Model

I have heard it said that time is more precious than space because we can reuse space but not time. What if we treat space with this much reverence? What is generally known about models of ...
294 views

### Is this partition problem strongly NP-complete?

Some computational problems have variants that appear to be harder. For instance, Graph Automorphism (GA) problem has quasi-polynomial time algorithm ( by Babai's Graph Isomorphism result) while the ...
113 views

### maximize edges minus vertices in a weighted graph

for a given weighted vertices and edges graph, we want to find the maximum subgraph. the maximum subgraph is made of some vertices and some edges of the given graph which sum of the edges minus sum of ...
153 views

### Best polynomial-time approximation factor for NP-optimization problems

Let us say that a function $f(n)$ is the best approximation factor for an NP-optimization problem, if both of the following hold: There exist a polynomial-time algorithm $A,$ and an integer $n_0$, ...
74 views

### Why can't a left-recursive, non-deterministic, or ambiguous grammar be LL(1)?

I've learned from several sources that an LL(1) grammar is: unambiguous, not left-recursive, and, deterministic (left-factorized). What I can't fully understand is why the above is true for any LL(1)...
506 views

### Feel dissatisfied after each submission

I am a third year graduate student at a "top-20" university who works on fine-grained complexity (lots of playing with 3-SUM, OV and the usual popular hardness conjectures). I have been fairly ...
110 views

### Grid-Minor Theorem of Robertson and Seymour and its Algorithmic Applications

Graph-Minor Theorem of Robertson and Seymour [1] states that if graph G has large treewidth, then it contains a large grid as minor. Most approximation results on general classes of graphs with ...
107 views

### Strong seeded randomness extractors with low entropy loss

I would like to implement a strong seeded randomness extractor for flat sources as a part of my project. Most of the literature on seeded extractors is concentrated on minimizing seed length. ...
176 views

### What is a good route for a math student to self study computer science systematically and efficiently?

I decided to ask this question after being attracted by how much one can do with the knowledge in computer science, including iOS application development, game(or mods) development, website creating, ...
122 views

### Separating words and graph isomorphism

I wonder if there are any known implications of Babai's recent quasi-polynomial time algorithm for Graph Isomorphism to separating words by DFA's. In both cases the ultimate goal is to differentiate ...
108 views

### Busy Beaver Equivalent for the Untyped Lambda Calculus

In the same way that the Busy Beaver function is defined for Turing Machines, we could define a similar function for the untyped lambda calculus: Over all terms in the ULC composed of ...
163 views

### Hamiltonian cycle vs co-NP [closed]

I am trying to understand co-NP and its implications properly. The French Wikipedia page describing co-NP provides the "complementary" version of the Hamiltonian cycle in co-NP as follows: ...
802 views

### What to do as a Theoretical computer science PhD student in a free time?

I am a mid-stage theoretical computer science student. Although I have a busy schedule, I still have a one or one a half hour in a day which I devote to reading and solving the question given Jeff ...
30 views

### Pass ordering for greedy local search algorithms

Apologies in advance for the slightly general question - I'm really looking for pointers to research / good keywords to look for. I have a problem with the following setup: I have a (finite) totally ...
216 views

### Is a binary sequence computable iff the Kolmogorov complexity of its initial segments is bounded?

Disclaimer: I am mostly unfamiliar with theoretical computer science, making it hard for me to navigate literature in the field. I ask the following out of curiosity. Background/Motivation: Coming ...
67 views

### Soundness of type (systems)

For someone without strong background in theoretical computer science: can soundness be a property of a type (given a type system), or a property of type systems only? In other words, can we say that ...
96 views

### Does ${\bf CFLPAD}={\bf PPAD}$?

What happens if we define ${\bf PPAD}$ such that instead of a polytime Turing-machine/polysize circuit, a (non-)deterministic finite/push-down automaton encodes the problem? I asked a similar ...
110 views

### Permuting the columns of a 0/1-matrix to avoid short segments

Consider an $n \times n$ table with $n$ stars such that each row contains at most $\log n$ stars. The stars break each row into segments (continuous parts of a row without stars). Let's call a segment ...
141 views

### Lower bound on the support size of an $\epsilon$-biased distribution

Let $D$ be an $\epsilon$-biased distribution we want to show that $$\text{Supp}(D)\geq \Omega\bigg(\frac{n}{\epsilon^2\log(\frac{1}{\epsilon})}\bigg)$$ I know that there are some proofs for this but I ...
203 views

### Does a given regular language contain an infinite prefix-free subset?

A set of words over a finite alphabet is prefix-free if there are no two distinct words where one is a prefix of the other. The question is: What is the complexity of checking whether a regular ...
60 views

### Which one of the following is the correct asymptotic notation? [closed]

While studying the complexity theory, I encountered a question which is as follows:- Which one of the following is correct? 1) θ(g(n)) = O(g(n)) ∩ Ω(g(n)) 2) θ(g(n)) = O(g(n)) ∪ Ω(g(n)) I know ...
115 views

I hope this is a suitable place to ask this question. An addition chain of size $n$ is a sequence $x_1, \dots, x_n$, where $x_1$ is fixed to 1 and $x_i = x_j + x_k$ for some $j,k < i$. I am ...
45 views