Bounty!

Problem. We study a local rewriting map defined on $5$-letter words over the alphabet $\{0,1,2,3\}$. A fixed forbidden-block set $\mathcal{F}$ of $16$ length-$3$ patterns is given by $$\mathcal{F}= \{000,001,010,011,100,101,110,111,112,121,122,211,212,221,222,333\}.$$ For any word $\mathbf{s}=s_1...

I am reading the book [Arora2009] and working on Exercise 1.3, which asks: EXERCISE 1.3. Complete the proof of Claim 1.6. Claim 1.6 states: Claim 1.6 Define a single-tape Turing machine to be a TM that has only one read-write tape, that is used as input, work, and output tape. For every $f: \{...

I am wondering if there can be such a thing as a persistent data structure for sequences that a) supports the following operations: insert(index, elem) in $O(log\, n)$ amortised time delete(index) in $O(log\, n)$ amortised time lookup(index) in $O(log\, n)$ while b) ensuring a canonical structu...

In dependent type theories, equality of terms is usually considered up to eta rules. This makes sense because it allows more pairs of terms to be equal. But experimenting a bit with type theory, I don't see how useful it is exactly - are there examples of things that are harder or impossible with...

I was playing around with $k$-ary searches, and found something interesting: This is the $\log(\frac{\text{time}}{\text{binary time}})$ to find an element in an array of length $100$ averaged over the search element in every position, against the $k$ of the search. Scaling up to $500$, we see a ...

I'm interested in gathering some solid arguments in favor of the Church-Turing thesis, which states that anything computable by an algorithm can be computed by a Turing machine. I understand that there are generally two kinds of arguments in support of the thesis: Empirical Arguments: These show...

Consider the following problem: Let $G=(V, E)$ be a weighted undirected graph with nonnegative weights. Let $S_1, S_2, \ldots, S_k\subseteq V$ be disjoint subsets representing vertices where you can fulfill errands $1, 2, \ldots, k$ respectively. Let $s\in V$ be a source vertex. Our job is to fin...

According to this post: Mathematicians have a habit of hijacking common nouns and adjectives for mathematical objects and properties, sometimes with good reasons such as geometric or other analogies or metaphors, and sometimes arbitrarily. Just look at "group", "ring", "space", "sheaf", "atlas", "...

According to https://pages.cs.wisc.edu/~cs812-1/adleman.pdf the complexity is stated to be $e^\sqrt{log_eq×log_elog_eq}$, but since the algorithm operates in a similar fashion than the Pohlig Hellman (on each prime factor of $q−1$), why is the complexity not about each such prime factor like Pohl...

I'm currently studying Computer Architecture / Computer Organization, and I'm struggling to find structured, high-quality resources to deeply understand a few specific topics. These are the four areas I’m focusing on: Register Transfer Language (RTL) and Register Microoperations Basic Computer ...

Given is a bipartite graph $G=(A,B;E)$ with $|B| = 2|A|$. Suppose we want to decide whether $B$ can be partitioned into two equal-size parts $B_1,B_2$ such that there is a perfect matching between $A$ and $B_1$ and another one between $A$ and $B_2$. This can be done in polynomial time, by duplica...

The book Sanjeev Arora and Barak defines class IP (interactive protocol) by making the verifier have private coins. Before proceeding to public coin proofs and showing they are the "same," the book mentions the following: The probabilities of correctly classifying an input can be made arbitraril...

Suppose we have a set $N$ of $n$ players and a set $M$ of $m$ items. We are given a matrix $P_{n \times m}$ whose element $p_{ij} \geq 0$ $(i \in N, m \in M)$ denotes the valuation of good $j$ by player $i$. Let $v = [v_1, v_2, \cdots, v_n]$ be a vector of valuation functions defined as $v_i(S) =...

I am reading up on Graham's algorithm and want to prove it's $4/3 - 1/(3m)$ optimality. To do that, we need to prove that if $j$ is the last job assigned to the most heavily loaded machine in the schedule returned by LPT and $l_j > \frac{OPT}{3}$, then Graham's algorithm returned the optimal make...

It was originally posted on MO. But don't got any answer. Basic background: A hydra is a finite rooted tree (with the root usually drawn at the bottom). The leaves of the hydra are called heads. Hercules is engaged in a battle with the hydra. At each step of the battle,Hercules chops off a head ...

Setting for the question $NP$ is either defined as class of languages where yes instances have polynomial verifiable certificates. Alternatively, it is defined in terms of polynomial-time nondeterministic Turing machines. A non-deterministic Turing machine $M$ is usually defined as having a speci...

Reading articles about calculating square root of an integer I stumbled across the pseudocode attached below. Original paper: T-count and Qubit Optimized Quantum Circuit Design of the Non-Restoring Square Root Algorithm by Edgard Muñoz-Coreas and Himanshu Thapliyal. ACM Journal on Emerging Tech...

I've encountered the following coloring problem: Suppose we have a complete graph with $n$ vertices, with each edge colored 0/1. We need to assign a 0/1 color to each vertex, too, such that the vertices in every pure-edge-color $k$-clique don't all share the same color as the edges, where $k$ is ...

I have been self-studying the performance of certain algorithms and I have come across a recurrence which I am not sure how to analyse the asymptotic performance. $ \begin{align} x_0 &= 0 \\ x_n &= x_{n-1} + g(n, x_{n-1}) \end{align} $ The function $g$ is in non-linear. I want to determ...

I was discussing context free languages with some friends, when we came up with the following language over the alphabet $\Sigma=\{a,b\}$: $$L=\{xy\mid |x|=|y|\land \#_a(x)=\#_b(y)\}.$$ Intuitively, the language is defined by all words of even length having the same number of $a$s in the first ha...

In the usual knapsack problem, there are $n$ items with values $v_1,\ldots,v_n$ and costs $c_1,\ldots,c_n$ and a total budget $B$, and the goal is to select a subset of items with maximum total value among those subsets with total cost at most $B$. This problem is NP-hard, but it has an FPTAS. In...

I have been revisiting selection networks with compare-exchange elements (CEs), in particular with K. Cong et al.: "Revisiting Oblivious Top-𝑘 Selection with Applications to Secure 𝑘-NN Classification" (2023). Over keeping the sequence count 2e for some natural number e (allowing a "perfect" bi...

By infinitely integrable function, what I mean is that you can (symbolically) integrate as much as you want and the function would still be elementary. Does iterative integration simulate arbritary computation? For clarity: We would assume an access to an oracle that can calculate symbolic integ...

In the reduction from the circuit value problem to unit resolution in this textbook (section A.6.1), they show how the gates are done. But they don't talk explicitly about how the inputs are encoded or how to actually form the final contradiction to create the empty clause. I'll use an AND gate w...

Purely relational databases (SQL) seem to suffer to nowadays from the lack of a good solution for search/indexing hierarchies. Here a systematic review of the subject: https://stackoverflow.com/q/4048151 What is surprising is that no "Lineage Column" solution makes use of a bit string column, i...

See below code: vector<long long> temp; for (int i = l; i <= r; ++i) { temp.push_back(holes[i]); } sort(temp.rbegin(), temp.rend()); long long needed_H2 = 0; for (int i = K; i < temp.size(); ++i) { needed_H2 += temp[i]; } Basically, it copies some range [l, r] of original array, sorts ...

For example, using GHCi, ghci> f x = x + 1 ghci> :t f f :: Num a => a -> a What is the type of the type signature f :: Num a => a -> a? Motivation I first encountered this question at work. Since I do not want to leak any information pertaining to my employment, I shall present a toy project in...

Given a bipartite graph G with bipartition $G = A \cup B$, and weights $w(v)$ for nodes of G such that $w(v)>0$ for $v \in A$ and $w(v)<0$ for $v \in B$. Let $V(G) = \{ v_1,v_2,..,v_n \}$. Call an ordering $v_1,v_2,.., v_n$ permissible if for each $ v_i \in B $, all its neighbours in $A$ appear ...

This happens to me from time to time: I compile my code with the highest optimization level (-Ofast) of the allegedly fastest compiler (GCC) of one of the fastest languages (C/C++). It takes 3 seconds. I run the compiled program, measuring performance. Then I make some trivial change (say, markin...

(not sure if this is a SO or a CS StackExchange Question, but I'm putting it here for now.) I've been working on a project developing a more extensible way to create synopses of ancient texts (essentially side-by-side comparisons with the diffs highlighted, but with options to focus only on sem...

For what example would Maekawa's algorithm allow out of timestamp order access to the critical section. It is mentioned that ordering is not satisfied in Maekawa's algorithm. But in what scenario would this be true? From my understanding, we will always have the queue at each process that follows...

I'm exploring a reduction from Exact 1-in-3-SAT (x3SAT) to the Subset Sum problem that allows the use of the Horowitz and Sahni algorithm, achieving a time complexity of $\mathcal{O^*}(2^{𝑛/2})$ for x3SAT. The reduction works as follows: Variables and Initialization: For each variable $u_i$ in...

My understanding is that an EBNF-style grammar (similar to a Context-Free Grammar (CFG) but with added optionals, repetition and/or grouping) defines a language, but doesn't correspond to a particular CFG. For example, the EBNF S -> a [b] . defines the language {"a b", "a"} and could be converted...

A monotonic stack is a stack whose elements are monotonically increasing or decreasing. To insert an element into the stack you need to remove elements that are greater/less than the provided element and then put the provided element on top keeping elements order. Usually, inserting in a monotoni...

Consider the following four variable Boolean function: $$F(A,B,C,D)=\sum(0,2,3,5,7,8,9,10,11,13,15)$$ If I show you the map, then what I get is: I have marked the Essential Prime Implicants with a bluer shade, which is $BD$ and $B'D'$. Then if I consider the prime implicants, there are four that...

Please refer to the paper Migacz, S., et al. (2019). Parallel implementation of a sequential Markov chain in Monte Carlo simulations of physical systems with pairwise interactions. Journal of Chemical Theory and Computation, 15(5), 2797–2806. Suppose I have $N=5$ particles: $A(1,4)$, $B(2,2)$, $C...

i can't find s-grammar(Simple grammar) for this language and s-grammar has the restricted form like A -> ax where A∈V, a∈T, x∈V*, and any pair (A, a) occurs at most once in production P. how can i find the s-grammar for this language? i found that the corresponding CFG for this language is: S ->...

This question builds from the well known Balanced graph partitioning. Given a graph G=(V,E) we want to divide the vertices V into k partitions P_k such that they all contain the same number of vertices and some objective function (example - minimum cost inside partition/minimum cost between parti...

A regular expresssion is defined recursively as $a$ for some $a \in \Sigma$ is a regular expression, $\varepsilon$ is a regular expression, $\emptyset$ is a regular expression, $(R_1 \cup R_2)$ where $R_1$ and $R_2$ are regular expressions is a regular expression, $(R_1 \circ R_2)$ where $R_1$...

I was reading these notes on approximation algorithms and I stumbled across a PTAS for an optimization version of the partition problem (essentially the Identical-machines scheduling $P_2 \|C_{\operatorname{max}}$ problem). It takes $O(2^{1/\varepsilon})$ time, which is very slow in terms of $\fr...

I have proposed an approximation algorithm for VCP that may produce a less than 2 approximation ratio. I know this contradicts what experts believe about the Unique Games Conjecture. However, I was hoping that experts could review my paper and identify any potential issues. Since last year and du...

Given an array of integers of size n, the task is to reduce the disturbance of the array where disturbance is counted as number of same neighbouring pairs. Ex: 2 1 2 2 1 1 The disturbance is 2. As two pair of neighbouring (2,2) and (1,1). The task is to reduce disturbance and the only operation...

A grid is divided up into red cells (pixels), black cells, and white cells. We want to find the smallest boundary that: All red cells are within the boundary All cells of the boundary itself are white The boundary can be irregular, but it must be continuous - no gaps or holes. What algorithm c...

Can someone explain how do we find these parity bit errors?

I learned that if the alphabet is limited to some constant size, e.g. {0,1} and maybe some special characters, we can still construct any Turing machine by simply expanding the state and encoding each original alphabet symbol in 0/1s. I was wondering if the same is true if we limit the state to s...

Computer A is connected to the internet using router RA that uses home NAT network. In the same way Computer B is connected to the internet using router RB that uses home NAT network. Lets look at a situation in which computer A sends a massege to computer B through the internet. Let's denote the...

Let G be a directed graph with non-negative weights. We call a path between two vertices an "odd path" if its weight is odd. We are looking for an algorithm for finding the weight of the shortest odd path between any two vertices in the graph. If possible, describe one algorithm that is reducti...

I've been reading Brent's original paper and struggling with his worst-case bounds derivation. (I won't even bother with the expected behavior analysis.) I get the Floyd's algorithm analysis as that's straightforward. For simplicity, take $q = 2, u = 0$ as in practice. Intuitively after each oute...

A class $∁$ is closed under polynomial time reductions if for every two languages $L_1, L_2$ such that $L_1 \leq_p L_2$ and $L_2 \in ∁$, it holds that $L_1 \in ∁.$ How to Show that for every $𝐿_1 ∈ \text{DTIME}(2^{𝑛^2})$, there exists $𝐿_2 ∈ \text{DTIME}(2^𝑛)$ such that $𝐿_1 \leq_p 𝐿_2$? My...

In the following G is directed graph and circuits are not necessarily simple. $$\text{2CIRC}_{1/2} = \left\{\langle G=(V, E) \rangle : G \text{ contains two or more cycles of length }\frac{|V|}{2}\right\}.$$ Reminder: two cycles are different from each other if they have at least one different ...