All Questions

Let $\ell> 1$ be an integer and consider the mapping $\text{Tr}:\mathbb{F}_{2^\ell}\to\mathbb{F}_{2^\ell}$ defined by $$\text{Tr}(x)=x^{2^0}+x^{2^{1}}+\cdots+x^{2^{\ell-1}}$$ It is then possible to ...

Whether there are some results on solving formal languages problems using mathematical analysis, continuous mathematics. For example, solving the intersection non-emptiness problem for a context-free ...

My question is about efficiently computable bijective functions. Informally I'm interested in: If a bijection is computable in polynomial time, can we compute it by a polynomial number of bijective ...

Unless I'm mistaken, a language of the form $\{0^a10^b\mid R(a,b)\}$ is context-free if and only if $R$ is a finite union of linear (in)equalities involving integer constants and the variables $a$ and ...

By Circuit Minimization, I am referring to the following decision problem. Circuit Minimization Input: A bit string $x$ and a number $k$. Question: Does there exist a Boolean Circuit $C$...

Every Turing complete programming language can describe an algorithm that sorts sequences. Is it also true that every Turing complete language can describe an algorithm that sorts sequences in $\...

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^*\}$?

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

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

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

I came across a paper called "A Note on Succinct Representation of Graphs". It seems that in the discussion section they claim that for any problem $X$ that is $\mathrm{P}$-hard under projections, $\...

I have been working on a new approach for a subset sum exact solver, and the current state provides an algorithm operating on $O{n/2 \choose n/4}$, demonstrating as well the hardest target value is ...

In MAX-SAT, given a formula, we want to maximize the number of satisfied clauses: given a formula $\phi = c_1 \cap \cdots \cap c_n$, where each $c_i$ is a disjunction, we want to find the largest $k\...

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

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

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

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

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

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$, ...

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)...

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

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

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

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, ...

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

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

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: ...

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

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

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

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

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

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

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

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

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

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

Suppose we have a set $S$ of (fixed-size) graphs, many of which are isomorphic to each other. How do you find a minimum-size set $M$ of graphs such that every $g\in S$ is isomorphic to some graph in $...

I am looking for data-structures to store efficiently a set of points $E$ in an euclidean space of dimension $d$. In particular, I would like to be able to solve the problem of finding all the point ...

Suppose we take a language such as Agda and disable the features that make it consistent; for example, universe polymorphism, structural recursion checks and similar. Suppose then that we take a term ...

There's a nice post by Gil Kalai which outlines the inherent bias in stable matching algorithms quantitatively. In the traditional loyd shapeley algorithm for $n$ men and $n$ women, given randomly ...

From calculus, we know that if someone has a continuous function $f$, it is enough to know $f$'s values on the rationals in order to know $f$ on the entire line. In some sense, a "countable amount of ...

From the Wikipedia documentation, "the suspected relationship of BQP to other problem spaces" diagram suggests no intersection between NP-complete problems and BQP. Has this been demonstrated or not?

If a standard Earley parser (with proper handling of nullable non-terminals, see Section 4 of "Practical Earley Parsing" by Aycock and Horspool) is modified with LL(1)-style lookahead, does it then ...

I'm reading about the complexity classes related to quantum computation, currently I'm studying QMA class. A language is in QMA(c,s) if there exists a polynomial time verifier and polynomial $p(n)$ ...

$(k,j)$-projective clustering is the natural generalisation for k-clustering, in which one needs to find $k$ $j$-flats in $\mathbb{R}^d$ that minimizes the cost function as defined below: Given a $j$-...

Given an unsorted array, QuickSort has to touch each source element it is trying to sort multiple times before it declares an array as sorted. (notice how many times the 2 is touched [circled in red ...

While reading "Computational Complexity: A Conceptual Perspective" by Oded Goldreich, I have come across the following passage, which I simply cannot get my head around: Note that the general ...

I've been reading and learning about SAT solvers this week. If they can solve problems with thousands of variable quickly haven't we practically solved ANY problem that can be reduced to it, including ...

Consider there are $k$ stacks containing a total of $n$ elements. Each element is either red or blue. We have complete knowledge of each element's location and color. Only push and pop are allowed on ...