All Questions

3
votes
1answer
146 views

Algebraic construction of $\varepsilon$-biased sets

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 ...
9
votes
3answers
372 views

Continuous mathematics and formal language theory

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 ...
8
votes
1answer
167 views

Reversible polynomial circuit iff polynomial reversible circuit?

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 ...
5
votes
1answer
153 views

For which $R$ is $\{0^a10^b10^c\mid R(a,b,c)\}$ context-free?

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 ...
3
votes
0answers
97 views

Is Circuit Minimization $P$-hard under logspace reductions?

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$...
-3
votes
2answers
160 views

Do Turing complete languages automatically have efficient algorithms [closed]

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 $\...
10
votes
3answers
313 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^*\}$?
6
votes
1answer
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 ...
0
votes
2answers
209 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 ...
1
vote
0answers
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 ...
14
votes
0answers
432 views

Is there a P-complete language X such that succinct-X is in P?

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, $\...
3
votes
0answers
233 views

new subset sum approach results

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 ...
2
votes
1answer
92 views

Maximum-minimum satisfiability

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\...
3
votes
2answers
110 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 ...
1
vote
1answer
80 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....
6
votes
0answers
143 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 ...
5
votes
2answers
303 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 ...
1
vote
1answer
115 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 ...
2
votes
0answers
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$, ...
0
votes
1answer
76 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)...
12
votes
3answers
513 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 ...
6
votes
0answers
112 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 ...
4
votes
1answer
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. ...
3
votes
0answers
177 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, ...
7
votes
1answer
126 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 ...
3
votes
0answers
113 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 ...
0
votes
3answers
166 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: ...
2
votes
2answers
822 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 ...
1
vote
0answers
31 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 ...
6
votes
1answer
224 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 ...
-3
votes
1answer
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 ...
8
votes
0answers
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 ...
0
votes
1answer
111 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 ...
3
votes
1answer
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 ...
10
votes
2answers
224 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 ...
-2
votes
1answer
61 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 ...
5
votes
0answers
117 views

Evaluating addition chains

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 ...
1
vote
0answers
46 views

Is there an efficient way to reduce a set of graphs under isomorphism?

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 $...
1
vote
0answers
72 views

Points of a finite set wihtin a ball

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 ...
4
votes
1answer
185 views

Can a term on normal form prove an illogical assertion?

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 ...
1
vote
0answers
40 views

Optimally fair stable matching

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 ...
5
votes
1answer
157 views

Minimal information needed for determine some function

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 ...
1
vote
1answer
147 views

Does BQP contain any NP-Complete problem?

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?
1
vote
0answers
35 views

Does an Earley parser equipped with LL(1)-style lookahead parse in linear time for all LL(1) grammars?

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 ...
-1
votes
1answer
46 views

QMA definition of difference between probabilities intuition

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)$ ...
1
vote
0answers
35 views

PTAS for projective clustering : survey

$(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$-...
-4
votes
2answers
82 views

Is it possible to have a sorting algorithm that computes faster than QuickSort? [closed]

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 ...
7
votes
1answer
107 views

Why is the “general notion of a reduction […] inherent to the notion of self-reducibility”?

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 ...
8
votes
0answers
180 views

SAT Solvers and their applications

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 ...
5
votes
1answer
65 views

Pop desired elements on stacks of bounded capacity

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

15 30 50 per page