All Questions

9,986 questions
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 ...
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 ...
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 ...
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 ...
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$...
160 views

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

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