Reference-request is used when the author needs to know about work related to the question.
4
votes
1answer
116 views
Splitting line segments with a line
Given is a finite set $S$ of line segments in the plane.
I am interested in finding a line $l$ which splits some segments in $S$ into two, thus yielding a new set of line segments $S'$.
Here ...
4
votes
2answers
409 views
Certified compiler and optimizations in Coq/Agda
I am interested in verified compilers formalized in Martin-Löf type theory, i.e. Coq/Agda. At the moment I’ve written a small toy example. Therewith I can prove that my optimizations are correct. For ...
11
votes
1answer
279 views
Winning strategy of an “edge or isolated vertex” deletion game
Is this perfect information game played on graphs know/studied?
Given a graph $G= (V,E)$, two players alternate picking an edge or an isolated node. If the player picks an edge $e = (u,v)$ the two ...
0
votes
0answers
169 views
Hypergraph decompositions used in TCS?
I am looking for general or notable theory and applications of hypergraph decompositions in TCS. For example:
there is a modular graph decomposition [1]. Has it or anything like it been extended to ...
2
votes
4answers
464 views
Applications of Game theory in computer science?
As a computer science student, I have been introduced to game theory, but not seen much detail on the subject. I have searched on Google and looked at some books about game theory and they provided ...
6
votes
0answers
110 views
Numerical stability of Simplex method
The simplex algorithm is often treated either within real arithmetic, or in the discrete world with exact computations. However, it seems to be implemented most often with floating-point arithmetic.
...
-1
votes
1answer
172 views
Find the maximum flux path between two nodes [closed]
Given a graph $G$ and two vertices $s$ and $t$, I want the maximum flux path from $s$ to $t$.That is, imagine $G$ to be a flow network with capacities on the edges. I want to find a single path that ...
2
votes
0answers
129 views
Is this variation of the “sequencing with release times and deadlines” problem NP-complete?
The following problem is known to be NP-complete. It can be found in pages 236 and 70 of Garey & Johnson. In this book this problem is known either as ...
13
votes
2answers
385 views
Does existence of a total $\mathsf{NP}$ search problem not solvable in polytime imply $\mathsf{NP}\cap\mathsf{coNP} \neq \mathsf{P}$?
It easy to see that if $\mathsf{NP}\cap\mathsf{coNP} \neq \mathsf{P}$ then there are total $\mathsf{NP}$ search problems which cannot be solved in polynomial time (create a total search problem by ...
7
votes
1answer
230 views
Recent Probabilistic Methods in Combinatorics and its appplications to Complexity Theory
I read the famous book by Alon and Spencer on the probabilistic method in combinatorics.
Is there a survey or lecture notes on recent advances and relationships with the following complexity ...
16
votes
1answer
245 views
Consequences of $BQP \subseteq P/poly$?
While Adleman's theorem shows, that $\mathsf{BPP} \subseteq \mathsf{P}/\text{poly}$, I'm not aware of any literature investigating the possible inclusion of $\mathsf{BQP} \subseteq ...
0
votes
0answers
73 views
Edge Cut of interval graphs
On interval graphs, minimal vertex separators are well understood: they are cliques, there are no more than $n$ ones. However, when we turn to the minimal edge cut, my search found no even one single ...
25
votes
1answer
775 views
Prerequisite for learning GCT
It seems that Geometric Complexity Theory requires much knowledge of pure maths such as algebraic geometry, representation theory.
While I am a CS student and do NOT have classes of very abstract ...
17
votes
6answers
819 views
Golden ratio or Pi in the running time
There are many places where the numbers $\pi$ and $(1+\sqrt5)/2$ show up. I'm curious to know about algorithms whose running time contains the golden ratio or $\pi$ in the exponent.
-6
votes
1answer
104 views
Minimizing edges of an FSM [closed]
There are various well-understood, efficient, and theoretically interesting algorithms to minimize a DFA in terms of states.
Is there research into minimizing based on edges of the FSM?
edit: ...
0
votes
0answers
85 views
Fullness of regular expressions with exponentiation
Meyer & Stockmeyer proved many years ago that the following problem is NEXPSPACE complete, called "fullness of regular expressions":
Input: regular expression with exponentiation
Output: true if ...
4
votes
1answer
152 views
Finding the closest point to a sets of discrete points
In a paper I am reviewing, the authors define the following problem and construct an algorithm. They give no further references and I suspect it has appeared somewhere in the literature before.
Let ...
7
votes
0answers
118 views
Boolean formula balancing in $\mathsf{AC^0}$
I am looking for references about the complexity of Boolean formula balancing problem. In particular,
Was it known that Boolean formulas can be balanced in $\mathsf{AC^0}$?
Is there a simple proof ...
8
votes
0answers
148 views
“Verifiable information”: is this a known concept?
The following seems to me like a natural definition and I wonder whether it's been studied somewhere
Consider $\mathsf{X} \subset 2^{\lbrace 0, 1 \rbrace^*}$ a set of languages.
Then $K \subset ...
2
votes
0answers
101 views
Generalizing linear interpolation to posets
Assume that I have an array $A$ of $n$ numerical values where some are known and some are unknown (with $A[0]$ and $A[n-1]$ assumed to be known). If I want to estimate an unknown value $A[i]$, a ...
0
votes
2answers
100 views
iterations of a $\epsilon$-FSM transducer on a tape as equivalent to a TM computation
A question partly inspired by a recent question[1] on the utility of FSMs: Years ago noticed the following property of FSM transducers with $\epsilon$-transitions (which allow an "empty" transition ...
7
votes
0answers
128 views
mixed vs behavior strategies for zero-sum game with infinite extensive form
This is a crosspost of this post on math.stackexchange, which didn't get any responses.
For two-player games given in extensive ("game tree") form, there are several natural ways to define randomized ...
3
votes
1answer
201 views
Stochastic version of a strongly NP-Complete problem
Does a strongly NP-Complete problem remain strongly NP-Complete if the variable set on which the objective/cost function depends are made stochastic ?
The problem Tree CVRP(Capacitated Vehicle ...
2
votes
3answers
183 views
References on model checking and pi calculi
I'm a mathematician and it looks like I need to learn about these topics. What would be good references that go into the technical details of the following topics?
(s)pi calculus
model checking
I'm ...
4
votes
2answers
146 views
Optimal upper bound on the number of non-isomorphic graphs with certain parameter
What are the optimal (or best known) bounds (preferably exact or else asymptotic but not expectation on random graphs) on the number of non-isomorphic (unlabelled) simple (no self-loop), undirected ...
6
votes
1answer
172 views
Are there applications of modular graph decomposition in TCS/complexity theory?
What are there some applications of modular graph decomposition in TCS/complexity theory?
I am especially interested in its use in proofs or upper/lower bounds if it occurs.
[1] Modular graph ...
11
votes
1answer
273 views
Does Conway's PRIMEGAME generate all prime powers of 2?
Most sites I have visited reading on this interesting topic state something along the lines
"the only powers of two (other than 2 itself) that occur in this sequence are those with prime exponent" ...
4
votes
0answers
168 views
Distributed algorithms on sets
Given a connected arbitrary network $G = (V,E)$, where $V$ is a set of nodes (processors) and $E$ is the set of edges between the nodes. Each node $v _i$ is assigned a non-empty set $S(v _i)$, where ...
5
votes
0answers
97 views
Upperbound on the degree of a boolean function in terms of its sensitivity
A very interesting open problem in the study of complexity measures of Boolean function is the so called sensitivity vs block sensitivity conjecture. For background on sensitivity versus block ...
7
votes
1answer
113 views
Complexity results for Lower-Elementary Recursive Functions?
Intrigued by Chris Pressey's interesting question on elementary-recursive functions, I was exploring more and unable to find an answer to this question on the web.
The elementary recursive functions ...
2
votes
0answers
88 views
Impractical problems in P [duplicate]
Possible Duplicate:
Polynomial-time algorithms with huge exponent/constant
In many texts you find statements like 'The class P characterizes the problems that are efficiently solvable. Even ...
7
votes
2answers
352 views
Why is the consensus problem so important in distributed computing?
In distributed computing, the consensus problem seems to be one of the central topics which has attracted intensive research. In particular, the paper "Impossibility of Distributed Consensus with One ...
13
votes
3answers
490 views
0-1 Linear Programming: computing the Optimal Formulation
Consider the $n$ dimensional space $\{0,1\}^n$, and let $c$ be a linear constraint of the form $a_1x_1 + a_2x_2 + a_3x_3 +\ ...\ + a_{n-1}x_{n-1} + a_nx_n \geq k$, where $a_i \in \mathbb{R}$, $x_i \in ...
8
votes
1answer
261 views
Online Algorithms books
Are there any recent books on Online Algorithms? I know of only two books on the subject.
Online Computation and Competitive Analysis by Allan Borodin and Ran El-Yaniv: This is a classic but old ...
9
votes
1answer
150 views
Noisy Parity (LWE) lower bounds/hardness results
Some background:
I'm interested in finding "lesser-known" lower bounds (or hardness results) for the Learning with Errors (LWE) problem, and generalizations thereof like Learning with Errors over ...
20
votes
2answers
466 views
Balls and Bins analysis in the $m \gg n$ regime: gaps
Suppose we are throwing $m$ balls into $n$ bins, where $m \gg n$. Let $X_i$ be the number of balls ending up in bin $i$, $X_\max$ be the heaviest bin, $X_\min$ be the lightest bin, and ...
13
votes
2answers
159 views
Combinatorial characterization of exact learning with membership queries
Edit: Since I haven't received any responses/comments in a week, I'd like to add that I'm happy to hear anything about the problem. I don't work in the area, so even if it's a simple observation, I ...
7
votes
2answers
150 views
Resumption-based IO systems?
I've been playing around with resumptions lately, mostly from Abramsky's classic paper Retracing Some Paths in Process Algebra. They are quite slick (basically solutions to the domain equation $R = I ...
1
vote
0answers
33 views
Lower bounds for minimum variance estimators in limited space
Cramer-Rao, Rao-Blackwell and Lehmann-Scheffé, all give you ways to prove that a statistical estimator has the lowest variance possible. Is there any CS related work on the minimum variance ...
14
votes
1answer
263 views
Complexity class associated with exhaustive search
What is the complexity class associated with exhaustive search algorithms? (if there is one)
Is it NP or PSPACE?
Are there restricted models of computation capturing the class of exhaustive search ...
7
votes
0answers
122 views
Minimum weight expander
Expander constructions given an expander which is a sub-graph of a complete graph. Sometimes we don't want to construct an arbitrary expander, want to find an expander inside another given graph. In a ...
2
votes
1answer
108 views
Independent iterations in Las Vegas algorithms
In [Randomized Algorithms, Motwani and Raghavan] book, it is stated that the method of independent iterations to reduce the error probability in Monte Carlo algorithms (amplification according to ...
8
votes
1answer
200 views
The complexity of the puzzle game Net
Net (known also as FreeNet, or as NetWalk) is a puzzle game played on a $n \times n$ grid with the following objects:
there are $m$ computers ; each computer occupies one cell and has one link ...
4
votes
1answer
138 views
Is semantic language complexity class UP Turing equivalent to syntactic language complexity class US?
${\sf UP}$ is defined in terms of unambiguous-SAT which asks if there exits at most one solution or no solution. On the other hand, ${\sf US}$ is defined in terms of unique-SAT which asks if there ...
10
votes
3answers
415 views
Recent publications on NP ?= coNP question
I am interested in the question of whether NP is equal to coNP or not. I'd much appreciate some advice on good publications to read on the topic.
For the record, I know that this question is ...
4
votes
1answer
283 views
Semantics of concurrent languages
I've seen that the preferred way to specify the semantics of a concurrent language is to use a process calculus (e.g. pi calculus, join calculus). But in the paper presenting the F# asynchronous ...
5
votes
1answer
120 views
Equivalent embeddings of a graph
I have difficulties finding a good definition of two embeddings of a (planar) graph in the plane being equivalent.
Intuitively I mean by equivalent that the embeddings look the same up to ...
6
votes
1answer
59 views
Hidden constant in eps-sample size computation
Given a range space $(X,R)$ with VC-Dimension $\le d$, we can create an $\varepsilon$-sample with probability at least $1-\delta$ by sampling $ ...
2
votes
2answers
262 views
what does “lifting” mean?
I see in certain places "lifting computation" or "lifting" mentioned. I haven't been able to accurately define for myself what is meant by that.
This usually comes up in computer science context. Any ...
22
votes
3answers
829 views
Ecology and evolution through the algorithmic lens
The study of ecology and evolution is becoming increasingly more mathematical, but most of the theoretical tools seem to be coming from physics. However, in many cases the problems have a very ...
