# All Questions

10,209 questions
Filter by
Sorted by
Tagged with
0answers
2 views

### How to prove a convex set is nonempty or empty in polynomial time?

I know ellipsoid method and interior method, but I do not find specific theorems to explain my question. I think that is a simplier question than optimizing an objective over a convex set. Can I use ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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$?
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
1answer
66 views

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

15 30 50 per page