Title: A New Mixed-Integer Programming Model and Solution Approach for the Two-Dimensional Non-Guillotine Cutting Problem

In this talk, I will consider a new mixed-integer linear programming model for the two-dimensional non-guillotine cutting problem. This model presents a relatively small number of binary variables. However, due to a potentially large number of constraints, difficulties may arise when one tries to solve the model directly. Therefore, a partitioning solution approach is developed. Computational results with problem instances of the literature as well as with larger randomly generated instances show the efficiency of the proposed partitioning scheme.

Title: Stealth Probing and Byzantine Tomography

IP routing is notoriously vulnerable to accidental misconfiguration and malicious attack. Although secure routing protocols are an important defense, the data plane must be part of any complete solution. Existing proposals for localizing data-plane failures in a secure fashion are heavy-weight, requiring cryptographic operations at each hop in a path. Instead, we propose to achieve fault localization by combibing a light-weight secure availability monitor (called ``stealth probing'') and a higher-level network management procedure that combines the results of probes from different vantage points (called ``Byzantine tomography'').

Title: Online Geometric Reconstruction

Suppose a structured dataset (set of numbers, set of points, a graph, etc.) get affected by noise and loses its properties. Can we efficiently modify the data minimally to ensure that it regains those properties? And can we do so in an online fashion using a procedure that requires sublinear time?

I will discuss the problem of reconstructing a convex terrain. From a geometric perspective, these results essentially talk about many neat properties (regarding convexity) of 3-D terrains.

Title: Clusters in a Multigraph with Elevated Density

Let G be a multigraph with the maximum degree Delta and density Gamma. We show that if Gamma > Delta, the collection of minimal clusters (maximally dense sets of vertices) is cycle-free. We also prove that for multigraphs with Gamma > Delta + 1, the size of any cluster is bounded from the above by a function, which depends on Delta and Gamma only. Finally, we show that two well-known lower bounds for the chromatic index of a multigraph are identical.

Title: On the Identity Testing Problem

Identity Testing is the following problem: given an arithmetic circuit C with coefficients from some field F, determine if the polynomial computed by the circuit is the identically zero polynomial or not. This problem admits a simple and efficient randomized polynomial-time algorithm but no deterministic polynomial-time algorithm is known.

We give an efficient deterministic algorithm for a very special class of circuits - circuits of depth three having bounded top fanin.

Title: Towards the Design of Robust Interdomain-Routing Protocols

In this talk, I will briefly review recent work by myself and others on the theoretical foundations of path-vector protocols. The most popular such protocol is the Border Gateway Protocol (BGP), today's standard protocol for interdomain routing on the Internet. This work is motivated by a need to develop rigorous methods to understand routing anomalies witnessed on the Internet, to assert provable guarantees abuot protocol behavior, and to suggest design guidelines for future modifications to or replacements for Internet routing protocols. The problem is an interesting one to model, because the Internet is a large, heterogeneous network in which routing decisions depend on uncoordinated, distributed inputs based on very diverse interests.

Title: Phase Transitions in Optimization Problems, and Algorithmic Implications

Phase transitions in random structures are an essential feature of statistical physics, play an important role in discrete mathematics, and have algorithmic implications. Some of the most interesting questions center around random 3-Sat (the satisfiability of randomly generated Conjunctive Normal Form formulas with 3 literals per clause), but because this is so hard to analyze, we often instead prove results for constraint satisfaction problems with clauses of length 2. For example, it is known that random 3-Sat undergoes a phase transition from almost-sure satisfiability to almost-sure unsatisfiability as the "clause density" increases, but it is not known exactly where this transition occurs, or even that the transition point tends to a constant. By contrast, the transition of random 2-Sat at density 1 is already a classical result, and more recently the transition's "scaling window" has been comprehensively analyzed. While 2-Sat is an easy decision problem, its optimization equivalent, Max 2-Sat, is NP-hard, and undergoes a similar phase transition, with the same scaling window. On the algorithmic side, it is known that sparse instances of random 3-Sat can, with high probability, be satisfied by efficient algorithms, but it is not known if this persists right up to the phase transition point. For "semi-random" 2-variable constraint satisfaction problems (a class encompassing random Max 2-Sat and random Max Cut), an algorithm running in expected linear time optimally solves instances of density up to the giant-component threshold, and indeed through the scaling window.