All Questions

Filter by
Sorted by
Tagged with
-1
votes
0answers
26 views

Functions Associative with Respect to Application

How to construct λ-terms, which are associative with respect to application? E.g., how to construct f and g, such that for any x: f (g x) = (f g) x (i.e. f g x) How to construct some closed set ...
1
vote
1answer
70 views

Consequences/existence of problems without any “optimal” algorithm

Let $P$ be some kind of "problem" such as addition or graph coloring, that has an input size $n$. Let $S_P$ denote the set of algorithms $A_1, A_2, \dots$ which deterministically solve $P$. Based off ...
0
votes
0answers
30 views

Knapsack Variant

I’m looking for algorithms to solve the following Knapsack variant: Given: A Knapsack of fixed size; A set of K item types. Item size within each type may be chosen/selected/solved-for between two ...
6
votes
1answer
131 views

3-coloring planar graphs in $O\left(3^{n^.5}\right)$?

I was wondering if the task of searching for planar 3-colorings is known to be of complexity $O\left(c^{\sqrt{n}}\right)$ or lower? This feels like it would be an intuitive consequence based from ...
-4
votes
0answers
38 views

How to prove of disprove the following Control Flow Graph theory

See the attached image for some background on Control Flow Graph In a single-entry, single-exit control flow graph (CFG), a node u post-lead v if every path from v to the exit includes 𝑢. Let q be ...
1
vote
0answers
39 views

State of the art Luby Transform code usable in Raptor codes?

I've just read Raptor Codes by Amin Shokrohalli which introduces linear-time fountain codes that needs $(1 + \varepsilon)k$ output symbols to recover the $k$ input symbols with high probability. A ...
5
votes
0answers
148 views

Nondeterminstic Linear Time vs Other Complexity Classes

Is it known whether or not nondeterministic linear time contains $P$ and/or smaller classes such as Uniform-$NC^1$?
0
votes
2answers
338 views

Formalizing and optimizing constraints involving booleans, pairs of booleans, and integer sums

My scenario has various flavors of SAT, constrained quadratic pseudo-Boolean, and integer programming. My attempts to formalize and solve the problem with Z3's ...
6
votes
1answer
131 views

Type-theoretic interpretation of Skolemization

What is the type-theoretic interpretation / equivalent of Skolemization? Skolemization converts some formula into Skolem normal form. The two formulae are equisatisfiable with each other. Or, to say ...
4
votes
0answers
71 views

Characterizing the ANF of Single-Cycle Boolean Permutations

Given a function $F: \{0, 1\}^n \to \{0, 1\}^n$, we say that $F$ is a boolean permutation (also sometimes called a vectorial boolean function or an s-box in the literature) if $F$ is a bijection. We ...
-2
votes
0answers
26 views

An efficient algorithm for maximizing gain by choosing from a set of options

(I hope this is on-topic for this site -- mods feel free to send this to another stack exchange if not ) I've got an optimization problem where I need to choose from one of several options to ...
8
votes
0answers
98 views

Model of Coq (pCuIC) in higher toposes?

Can the type theory of Coq (pCuIC) be modeled in all higher Grothendieck toposes? First of all, even the set theoretical model is not complete (e.g. inductive types in Prop). Although, this is ...
3
votes
1answer
81 views

Deterministic Realtime Languages

Book and Greibach (V. Book, Ronald & A. Greibach, Sheila. (1970). Quasi-realtime languages. Theory of Computing Systems. 4. 97-111. 10.1007/BF01705890.) prove that non-deterministic linear time ...
4
votes
1answer
66 views

Complexity of Parallelogram Range Minimum Query

Given an $n\times n$ array $G$, what is known about the complexity of parallelogram static RMQs? More formally, answering the query $$RMQ_P(a,b,c,d)=\min_{a\leq i \leq b \\ c \leq i+j \leq d}G[i][j]$...
1
vote
1answer
48 views

Correlation between noise resilience and output distribution of Boolean circuits

Given a randomly generated AND/OR tree (and negations), we can calculate the probability that the circuit will represent a specific Boolean function up to 3 input literals. Starting from 4 (or at ...
-1
votes
2answers
98 views

Hospital Resident Matching Algorithm with Incomplete Preferences

Consider a set of doctors $D$ and hospitals $H$ such that each doctor $d \in D$ has a rank ordered strict preference over a subset of hospitals, $H_d \subseteq H$. Similarly, each hospital $h \in H$ ...
-2
votes
0answers
66 views

Is BQP upper bounded by the class of problems computable by an exponential number of GPUs?

Consider the class $EXPGPU$ that informally contains all problems that can be stocastically solved in polynomial time by an exponential number of processors. Question: Is $BQP \subset EXPGPU$? My ...
12
votes
0answers
184 views

Does small circuits for a NP-complete problem contradict ETH?

The remarks of the Theorem 4 in the paper "On the complexity of circuit satisfiability" claims that: if circuit satisfiability (CktSat) problem can be decided by deterministic circuits of $2^{o(n)}$ ...
-2
votes
0answers
115 views

The Art of Computer Programming by Knuth [closed]

I recently got a Safari Books Online subscription and was excited to discover that it included The Art of Computer Programming. I've never been able to afford the paperback version, but now I have it ...
4
votes
0answers
128 views

A game on several graphs

Consider the following game on a directed weighted graph $G$ with a chip at some vertex. All vertices of $G$ are marked by A or B. There are two players Alice and Bob. The goal of Alice (Bob) is to ...
3
votes
0answers
87 views

Earliest forbidden subgraph characterisation

I wonder, what was the first non-trivial graph class for which there was a forbidden (induced) subgraph characterisation ? Of course, bipartite graph is one example but I am considering it as trivial ...
1
vote
0answers
48 views

Which algorithms can be used to measure similarity for two very different languages?

recently I have read this paper, A Survey of text similarity approaches, and I discovered that there are a lot of algorithms that can be used to measure similarity. At present I am applying the ...
1
vote
1answer
53 views

Are there digraphs such that any two arborescences are arc-disjoint?

Let $D=(V,A)$ be a directed graph with root $r$. An $r$-arborescence of $D$ is a subgraph such that for any $v\in V-r$, there is exactly one directed path from $r$ to $v$. Hence an $r$-arborescence is ...
2
votes
0answers
58 views

Algorithm for computing the smallest subset of nodes to remove from a graph to make it a tree

I have encountered an interesting problem that I couldn't find any references to solve: Determine the smallest subset of nodes that need to be removed from an undirected graph to make it a tree. ...
-3
votes
0answers
32 views

what does “approximable to within a factor” mean?

Can someone explain what this sentence itself means? For any a > 1, problem 1 (eg. ±PSC) is approximable to within a factor of 4.a-3, if problem 2 (eg. Min-M) is approximable to within a factor of a.
-4
votes
1answer
49 views

what does NP ⊆ DTIME(…) mean?

Recently I've seen inside theory of a paper. This time complexity, DTIME, is completely new for me. Can somebody explain it? Also, the paper shows that the misinformation containment problem cannot ...
5
votes
1answer
189 views

The asymptotic behavior of a recurrence related to stable matchings

I would like to provide asymptotic estimates for a sequence defined (for n a power of 2) as follows: $$a_1 = 1, a_2 = 2$$ $$a_n = 3a_{n/2}^2 - 2a_{n/4}^4$$ Apparently, Knuth was able to prove that ...
13
votes
5answers
429 views

When have we found better bounds for known algorithms?

Are there interesting instances of algorithms that have been published with proven bounds, and where strictly better bounds have later been published? Not better algorithms with better bounds - ...
-1
votes
0answers
24 views

A special type of pair matching case

Let's suppose we have a group of N members. We need to match the entire group or any subgroup based on the following criteria: Each group member has a matching index for another group member. 2.This ...
0
votes
0answers
41 views

Matching of two weighted graphs allowing one-to-many mapping

I am looking for a heuristic for a graph matching problem as follows. Given two graphs: $A$ (consisting of nodes $a_i$) and $B$ (consisting of nodes $b_i$). Typically the size of $B$ is larger than ...
-1
votes
0answers
28 views

LL(1) grammar without null productions

Every ll(1) grammar without null productions is SLR(1).what properties of ll(1) make above statement true?
1
vote
1answer
45 views

Equivalent formula for LTL with and without past operators

I have recently been researching LTL with and without past operators. From my understanding, both LTL and PLTL (LTL with Past) are equally expressive, however, PLTL is exponentially more succinct. I ...
-2
votes
0answers
60 views

Comparisons between Graph isomorphism algorithms

I have heard quite a few algorithms for isomorphism tests. Can anyone tell me which one is the best and their difference? More specifically, what is the relationship between Weisfeiler-Lehman and VF2 ...
-1
votes
0answers
70 views

Any worked examples of Block Sensitivity?

So this proof of the Sensitivity Conjecture is making interesting waves (ie. the conjecture is sufficiently interesting, and the proof is sufficiently small (Donald Knuth has it down to one page now......
0
votes
0answers
56 views

Language recongized by a “quasi realtime register machine”?

Counter machines are very powerful. Even two counters suffice for making these Turing complete. But, in simulating a Turing machine the counter machine encodes in its integers a large amount of data. ...
-3
votes
0answers
32 views

How to determine Reliability of a graph when defined as the probability of specific vertex being connected through a cycle?

Given a graph G and three nodes: a, b,c. The edges operate with probability p, nodes are perfect. Given a positive integer n, $R_n$ is defined as the probability that, nodes a,b and c stay connected ...
3
votes
1answer
80 views

Complexity of existence of simple polygonalization with prescribed area?

This is a followup on my previous question. Fekete proved the NP-completeness of deciding the existence of simple polygonalization with minimum (or maximum) enclosed area (simple polygonalization is ...
-2
votes
1answer
68 views

DPDA with parameterized states

I'm considering an extension of Sublime Text's syntax definition format. A syntax definition is, in essence, a specification of a deterministic pushdown automaton. I would like to extend the system to ...
9
votes
1answer
176 views

Proof for Upper Bound of Sum of Square Roots Problem

In [1], Garey et al. identify what would later be known as the Sum of Square Roots Problem in the course of working out the NP-completeness of Euclidean TSP. Given integers $a_1, a_2, \ldots, a_n$ ...
8
votes
1answer
878 views

On the sensitivity conjecture?

The recent establishment of the relation $bs(f)=O(s(f)^4)$ goes through Gotsman,Linial . Can the same approach get to $O(s(f)^2)$ or is there an essential limitation to the approach?
2
votes
1answer
126 views

Finding whether $n$ polytopes have nontrivial intersection from pairwise comparisons

I have a set of $n$ convex polytopes of the form $$\mathcal{L_i} = \{ \beta \mid C_i \beta \leq 0 \}$$ where $C$ is a matrix and $\beta$ is a vector. I know that for each pair of polytopes $$(\...
-1
votes
0answers
136 views

Complexity and completeness of certain problems resembling $BPP$ and $PP$?

Given a $3SAT$ formula in $n$ variables with promise that either it has $>(1-r)2^{n}$ satisfying solutions or it has $<r\cdot2^{n}$ satisfying solutions where $r\in(0,\frac12)$ is fixed decide ...
13
votes
0answers
147 views

Counting solutions to extended MSO formulas, and sampling — do these appear in the literature?

I am trying to determine if the literature contains various extensions of Courcelle's theorem. Since I haven't been able to find these in the literature, I guess that these are folklore results, or ...
0
votes
0answers
57 views

s,t-Graphs representing infinite number of addition chains

I am looking at directed acyclic multi-graphs $G=(V,E)$ with a single source and sink with integer labeled arcs. Each vertex has exactly two inputs except $s$. Each vertex has at least one output ...
1
vote
0answers
49 views

Directed Acyclic Graph partition into minimum subgraphs with a constraint

I have this problem, not sure there is a name for it, wherein a Directed Acyclic Graph has different colored nodes. The idea is to partition it into minimum number of subgraphs with the following 2 ...
2
votes
0answers
76 views

Sensitivity and Low-Degree Approximation under Non-Uniform Distribution

I am searching for generalizations of analysis of Boolean functions when the input strings are distributed according to a general non-uniform distribution, possibly with arbitrary dependencies between ...
4
votes
2answers
139 views

reference request for construction of expanders

I'm looking for a good exposition of the explicit constructive proof of the existence of expander graph families due to Reingold Vadhan and Wigderson. Arora/Barak has a chapter on it, but i find it ...
2
votes
0answers
70 views

Common techniques for the acyclic orientation problem under some special constraint?

An acyclic orientation of an undirected graph is an assignment of a direction to each edge(an orientation) that does not form any directed cycle and therefore generates a directed acyclic graph(DAG). ...
8
votes
1answer
333 views

Is convex optimisation in P?

Consider a convex optimisation problem in the form $$\begin{align} f_0(x_1, \ldots, x_n) &\to \min \\ f_i(x_1, \ldots, x_n) & \leq 0, \quad i = 1, \ldots, m \end{align}$$ where $f_0, f_1, \...
2
votes
0answers
66 views

Quantum security of cryptosystems

One of the main candidates for PQ cryptography is code based cryptography (other than lattice based). The Niederreiter cryptosystem based on goppa codes is shown to be resistant to hidden subgroup ...

15 30 50 per page