Most Popular
1500 questions
15
votes
6 answers
Advice for Graduate School in Computer Science
I am looking for some advice and feedback.
Background: I am an undergraduate mathematics student, with an interest in theoretical computer science (computational complexity, graph theory, combinatorics). I want to pursue a PhD in Computer Science…
Quaternary
- 325
- 2
- 9
15
votes
2 answers
What does 'gadget' mean in NP-hard reduction?
This question may not be technical. As a non-native speaker and a TA for algorithm class, I always wondered what gadget means in 'clause gadget' or 'variable gadget'. The dictionary says a gadget is a machine or a device, but I'm not sure what…
Federico Magallanez
- 591
- 4
- 8
15
votes
5 answers
What is the complexity class for quantum subroutines taking in arbitrary quantum states as inputs?
The complexity class BQP corresponds to polynomial time quantum subroutines taking in classical inputs and spitting out a probabilistic classical output. Quantum advice modifies that to include copies of some predetermined quantum advice states but…
Timmy
- 261
- 1
- 4
15
votes
2 answers
Best way to determine the minimum dimension of a structure given only distances between points
I came across this problem in an area of physics quite far removed from computer science, but it seems like the type of question that has been studied in CS, so I thought I'd try my luck asking it here.
Imagine you are given a set of points…
Joe Fitzsimons
- 13,675
- 47
- 91
15
votes
3 answers
Complexity theory when an oracle is part of the input
The most common way in which oracles occur in complexity theory is as follows: A fixed oracle is made available to, say, a Turing machine with certain limited resources, and one studies how the oracle increases the computational power of the…
Timothy Chow
- 7,550
- 35
- 43
15
votes
2 answers
Eliminating cofix in Coq proof
While trying to prove some basic properties using coinductive types in Coq, I keep running into the following problem and I cannot get around it. I've distilled the problem into a simple Coq script as follows.
The type Tree defines possibly…
Dave Clarke
- 16,666
- 3
- 60
- 106
15
votes
1 answer
Maintaining order in a list in $AC^0$ in $O(1)$ time
The order maintenance problem (or "maintaining order in a list") is to support the operations:
singleton: creates a list with one item, returns a pointer to it
insertAfter: given a pointer to an item, inserts a new item after it, returning a…
jbapple
- 11,184
- 2
- 29
- 50
15
votes
2 answers
Proof theory of biproducts?
A category has biproducts when the same objects are both the products and coproducts. Has anyone investigated the proof theory of categories with biproducts?
Perhaps the best-known example is the category of vector spaces, in which the direct sum…
Neel Krishnaswami
- 32,528
- 1
- 100
- 165
15
votes
2 answers
Reusing 5-independent hash functions for linear probing
In hash tables that resolve collisions by linear probing, in order to ensure $O(1)$ expected performance, it is both necessary and sufficient that the hash function be from a 5-independent family. (Sufficiency: "Linear probing with constant…
jbapple
- 11,184
- 2
- 29
- 50
15
votes
1 answer
Is the lower bound proof in this paper correct?
In this paper on "Circle Packing for Origami Design Is Hard" by Erik D. Demaine, Sandor P. Fekete, Robert J. Lang, on page 15, figure 13, they claim that the side length of the smallest square that encloses two circles of area 1/2 each is 1.471299.…
Vinayak Pathak
- 1,631
- 10
- 22
15
votes
1 answer
Triangulating a Planar Polygon
Are there by now simpler algorithms/proofs for triangulating a planar polygon in linear time? What is a good resource on the state of the art of this famous problem?
Gil Kalai
- 6,033
- 35
- 73
15
votes
3 answers
Sources for Algorithmic Evolutionary Game Theory
I use the title term in a very loose sense.
There is a significant amount of work on evolutionary game theory, including its mathematical foundations. I was recommended "Evolutionary Games and Population Dynamics" but haven't delved into it…
Elliot JJ
- 745
- 2
- 8
- 12
15
votes
2 answers
Has anyone used Pottier and Gauthier's polymorphic defunctionalization in a modular compiler?
Defunctionalization is a program transformation that converts higher-order programs into first-order programs. The idea is that given a program, there are only finitely many lambda-abstractions, so you can replace each lambda with an id, and each…
Neel Krishnaswami
- 32,528
- 1
- 100
- 165
15
votes
1 answer
Modular Decomposition and Clique-width
I am trying to understand some concepts about Modular decomposition and Clique-width graphs.
In this paper ("On P4-tidy graphs"), there is a proof of how to solve optimization problems like clique-number or chromatic-number using Modular…
user2582
- 531
- 3
- 8
15
votes
4 answers
What's new in compiler optimization techniques over last few years?
I'm interested in optimization of data flow and control flow graphs and in particular more computationally complex.
But it will also be interesting to know about the latest inventions in the field of peephole optimizations.
Evgeny Gavrin
- 253
- 1
- 7