# 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 ...
1answer
137 views

### About a pre-processing step for primal–dual weighted set cover problem

I was reading the paper titled "Primal-dual RNC approximation algorithms.." by Rajagopalan and Vazirani. I have a problem of understanding the Lemma 4.1.1. They present a dual fitting based algorithm ...
1answer
219 views

### Winning strategy in the game of triplets

The game of triplets is defined by a finite set of elements $X$, and a finite multi-set $T$ containing triplets of elements. Two players take turns picking elements from $X$ until all elements are ...
1answer
78 views

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 ...
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$ ...
1answer
66 views

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)}$ ...
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 ...
1answer
140 views

### Possibility of hierarchy with $UP$ class?

I am not sure if this is a cheap query. However I am unable to find this myself. So I am posting here. The standard complexity class is built with $NP$ and $coNP$ and leads up to $PSPACE$. The ...
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 ...
2answers
299 views

### Consequences of OWFs for Complexity

It it well-known that the existence of one-way functions is necessary and sufficient for much of cryptography (digital signatures, pseudorandom generators, private-key encryption, etc.). My question ...
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 ...
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 ...
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 ...
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. ...
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.
1answer
418 views

### What is the hardest instance for the group isomorphism problem?

Two groups $(G,\cdot)$ and $(H, \times)$ are said to be isomorphic iff there exists a homomorphism from $G$ to $H$ which is bijective. The group isomorphism problem is as follows: given two groups, ...
0answers
165 views

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

15 30 50 per page