I can't say off the bat whether I have openings. It depends on what funding I have, what projects I'm working on, and what I want to branch into. And these things vary throughout the year. But you first need to figure out if there is a likely match between us.

What is your basic requirement in a PhD student?
Any student I work with must have strong fundamentals in algorithms (like the content of the CLRS book). A quick check is: can you code Djikstra's algorithm from scratch, and prove that it is correct?
I have two kinds of projects, which require different kinds of students.

Theory: This requires a very strong mathematical background. While it's unlikely that you already know the requisite math for the project, you need the more elusive quality of mathematical maturity. This is the ability to learn new mathematical concepts, be able to get the intuition from the symbolism, and work with these new concepts. There is no simple way to get it. If you are a pure math major, then it's likely that you have this ability (otherwise, you wouldn't be a pure math major). If you're a CS major, here are some rules of thumb. You absolutely loved your algorithms and theory of computation courses, and you have taken some math courses such as real analysis, abstract algebra, graph theory (that are beyond the standard requirements). Proof writing is an absolute must. You need to have enough experience with reading and writing formal proofs, that would pass the standard of, say, an analysis course. Closer to the work I do, you would need to able to formally solve questions in the following books: "Graph Theory" by Diestel, "Randomized Algorithms" by Motwani-Raghavan, and "Computational Complexity" by Arora-Barak.

Applied: I do a fair bit of work in applied graph algorithms, and am usually looking for various applications of TCS. I require a strong ability in coding in C/C++ (for efficient algorithms), and strong scripting ability in Python (to run experiments and process data generated). You need to be able to think in terms of efficient code, design practical data structures, and know how to profile code to study it. You will need to do lots of experimentation on large datasets. You need to able to think like a scientist about doing rigorous algorithmic experiments. (This is harder to do, and typically students will pick this up with me. But you need to have basic critical thinking about empirically evaluating your algorithm.)

I need students with core strength in one of the above areas, and basic ability/interest in the other. I do both theoretical and applied work, and I like for my students to straddle this boundary. This is a highly desirable skill in both academia and industry, and is surprisingly uncommon. Naturally, my job is to help students grow, and I will try to train you so that you gain strength in both areas. But you need to have some basic foundation before we begin this process.

How do we begin to work together?
First, an overview of my mentoring structure. My typical group size is about 3-4 PhD students. I usually give each student a different project, though they are free to talk to each other about their work. I do this to ensure that every student has the chance to be come an expert in their own niche. Also, this reduces conflicts on primary ownership of the research work. I meet with every student one hour per week, where I give them my undivided attention. I brainstorm and work with them, to make sure they have an agenda for at least the next week.
Before you approach me, it is a good idea to try to read some of my recent papers. Naturally, it will be too much for you to figure out what's going on. But try to get some sense of the problems I work on, and which ones interest you. Generally, a careful reading of the abstract and introduction should be enough to figure out if you will like similar problems. Skim through the rest of the paper to get a sense of how we get such results.
When you approach me, tell me about what you read, and your thoughts on it. You can be free to tell me something was confusing, or didn't make sense. But I want to know what interested you, and I need to get a sense of whether you have the foundation to work on such problems. When we begin to work together, I will give you books or papers to build this foundation. After about two quarters to a year of preparation, we will begin the actual research. Depending on your interests and my assessment, I will suggest a few potential projects. You may choose one of them, or leave that to me. Within a month or so, I expect you to stick to the project for at least a year. (No buyer's remorse.) Every project looks exciting initially, before you hit a wall, and then it becomes boring. Research rarely yields fruit without long hours and effort.
Once we have decided a project, we will spend a few weeks making a plan of work for you. Initially, I will give well-defined concrete tasks for you, like implementing variations of an algorithm, presenting a paper/result to me, or trying to prove some specific claim. Eventually, these goals become more open-ended, and you will play a role in defining these goals.

What about working hours?
We will have hour long weekly meetings. Depending on the project and the current status, I may choose to also work offline on the project. But in general, you will do most of the work, since it is your PhD thesis. I may ask you to be available on campus, during some select hours a day or two per week. This is simply so that I can switch around our meeting time, if my schedule gets moved around (which happens annoyingly often). I do not keep track of where you are, whether you come to lab, how long you work, etc.
Quite frankly, if you do not put in at least 15 focused hours per week on your project, it won't succeed. I can easily tell if you do last minute work before our meeting, and you won't have much success winging it in our meetings. Generally, one hour of my time is equivalent to 8-10 hours of your time. Yes, you read that right. I am at least eight times more efficient than you are. It's not because I'm much smarter. No, it's because I've been doing research for so long that I have deeper intuition (that you will need to build). And building that intuition takes long hours, poring over a single project. It will often happen that you will spend a week coming up with an algorithmic or proof strategy, and I will shoot it down in 20 minutes. That does not disappoint me; quite the contrary, I'm happy that you're trying to think for yourself. This is your learning process and the curve is initially steep. But by putting those focused (emphasizing the focused) hours day after day, week after week, in a couple years, you will be teaching me new aspects of the problems we're working on.
You might wonder after a few meetings: how on earth can you keep up with me? I seem to know about so many papers, so many results, have many ideas, and shoot down your ideas rapidly. (It's simply experience.) Your solution is time. I am crazily busy; I have to teach, review innumerable papers, meet with other students, and juggle other projects. If I'm lucky, I'll put in 2 hours per week on our project. You have only one project, and only one goal. If you focus and spend all your time on that one project, you will gain the depth in that project to get ahead of me. It may take a few year, but that's why a PhD is five years long.