How to find biconnected components

Every serious competitive programmer knows how to find all bridges and articulation points in an undirected graph in linear time. Recently, however, I came across a problem that required finding the biconnected components explicitly, and I couldn’t figure out how to do it. The usual suspects, surprisingly, don’t explain it. Sedgewick’s Algorithms, 3rd ed., Part V discusses biconnectivity and explains how to find bridges, but does not explain how to find biconnected components. Skiena’s The Algorithm Design Manual gives code for finding articulation points, but similarly does not explain how to find biconnected components. After consulting some online sources, I saw that the idea is to maintain a stack of visited edges, and upon discovering a complete biconnected component in the course of DFS, pop the corresponding edges off.

Let’s review some definitions. A bridge in an undirected graph is an edge that, if removed, would increase the number of connected components. (Alternatively, a bridge is an edge that, if removed, would disconnect the connected component that it belongs to.) An articulation point of an undirected graph is a vertex that, if removed, would increase the number of connected components. Each endpoint of a bridge is an articulation point (unless its degree is 1) but the converse is false; some articulation points are not associated with any bridge. Consider a graph with 5 vertices, consisting of two triangles (i.e., complete graphs of order 3) that share a common vertex. It has no bridges, but the node common to the two triangles is an articulation point. A biconnected graph is a connected graph that has no articulation points; it remains connected if any single vertex is removed. A biconnected component of an undirected graph is a maximal biconnected subgraph. Every edge in an undirected graph belongs to exactly one biconnected component. Any two biconnected components may have at most one vertex in common; such a vertex is an articulation point.

The well-known classic DFS-based approach to find articulation points reachable from a given starting vertex is due to Hopcroft and Tarjan. Here is pseudocode:

// `num_visited` is the next preorder number
global num_visited := 0;
// `pre[v]` is the preorder number of `v`, if it has been visited
global pre: array;
global ap := {};
function dfs(v, parent) {
    pre[v] := num_visited;
    num_visited := num_visited + 1;
    // `low[v]` is the lowest preorder number reachable from `v` by following
    // zero or more tree edges and then at most one back edge
    low := pre[v];
    num_children := 0;
    for {w | w is a neighbour of v} {
        if (w = p) continue;
        if (pre[w] = nil) {
            // (v, w) is a tree edge
            num_children := num_children + 1;
            child_low := dfs(w, v);
            if ((p != nil and child_low >= pre[v]) or
                (p  = nil and num_children > 1)) {
                // a non-root vertex `v` is an articulation point iff from `w` we
                // could not reach anything visited strictly before `v`, while the
                // root is an articulation point iff it has more than one child
                ap.add(v);
            }
            low := min(low, child_low);
        } else {
            // (v, w) is a back edge
            low := min(low, pre[w]);
        }
    }
    return low;
}

(In case you forgot, the code to find bridges is very similar. The edge (v, w) is a bridge if and only if child_low is strictly greater than pre[v], with no special case for the root.)

Knowledge of the entire set of articulation points is not enough to construct the biconnected components explicitly. We know that for a non-articulation point, all incident edges belong to the same biconnected component, whereas for an articulation point, not all incident edges belong to the same biconnected component. Running the above algorithm to find all articulation points does not tell us which edges incident upon an articulation point belong to a common biconnected component. Instead, we have to modify the DFS algorithm. Some of the code online was either overly complicated or of dubious correctness, so I wrote my own. In the below pseudocode, changes from the previous code block are bolded, and comments from the previous code block are not repeated.

global num_visited := 0;
global pre: array;
global bicomp := {};
global stk: stack;
function dfs(v, parent) {
    pre[v] := num_visited;
    num_visited := num_visited + 1;
    low := pre[v];
    num_children := 0;
    for {w | w is a neighbour of v} {
        if (w = p) continue;
        if (pre[w] = nil) {
            num_children := num_children + 1;
            stk.push((v, w));
            child_low := dfs(w, v);
            if ((p != nil and child_low >= pre[v]) or
                (p  = nil and num_children > 1)) {
                // We just finished exploring a biconnected component starting with
                // the edge (v, w)
                current_bicomp = {};
                do {
                    e := stk.pop();
                    current_bicomp.add(e);
                } while (e != (v, w));
                bicomp.add(current_bicomp);
            }
            low := min(low, child_low);
        } else {
            low := min(low, pre[w]);
            if (pre[w] < pre[v]) {
                // (v, w) is a back edge, but still needs to be pushed because it
                // is part of the enclosing biconnected component
                stk.push((v, w));
            }
        }
    }
    return low;
}

One change from the code to find the articulation points is that we no longer need to keep track of the number of children. If the root has multiple children, then each time we take a tree edge from the root, we explore one biconnected component containing the root before returning. (The presence of multiple such biconnected components implies that the root is an articulation point.) For any non-root vertex v, each time we take a tree edge to a child from which no node that was visited strictly before v is reachable, we explore one biconnected component before returning. In each case, upon returning, we pop off all the edges explored and package them as a single biconnected component.

I don’t usually like to write pseudocode, because actual code is more precise, and I’m proficient enough in C++ that I can write actual code in C++ and have it be almost as readable as pseudocode (you might think of this as a weird flex). However, in this particular case, the implementation details are sort of annoying: when we mark an edge as belonging to a particular biconnected component, we generally will want to store the biconnected component ID of that edge alongside the edge itself in the adjacency list structure (for efficient traversal and lookup), and need to make sure that the reverse edge (which is, of course, the same edge, since this is an undirected graph, but is stored in a different row of the adjacency list) is also so marked. To see C++ code that does do this, see my solution to SPOJ STOPCITY. To see (Java) code that doesn’t mark the edges but just the vertices, indy256 comes to the rescue as always. (This representation doesn’t directly give you enough information to solve STOPCITY. You need to convert it into a forest where each node represents a biconnected component of the original graph, and two nodes are joined by an edge if the corresponding biconnected components share a vertex. Then, there exists exactly one pair of nodes (s', d') in this tree such that s' contains s, d' contains d, and the path from (s', d') does not pass through any other vertex that contains s or d. The answer is the set of all vertices that belong to any biconnected component corresponding to any node on the path from s' to d'.)

Armchair lawyering re: Sanchez v. Mayorkas

In Sanchez v. Mayorkas, the Supreme Court ruled 9–0 that if a person entered the United States without inspection, but was later granted TPS, that person is not deemed to be “inspected and admitted”, and therefore cannot establish eligibility for adjustment of status under INA 245(a) (8 U.S.C. §1182(a)).

At first, the ruling appears to be a straightforward reading of the Immigration and Nationality Act. The general adjustment of status statute, INA 245(a), provides as follows:

The status of an alien who was inspected and admitted or paroled into the United States or the status of any other alien having an approved petition for classification as a VAWA self-petitioner may be adjusted by the Attorney General …

INA 245(c)(2) also prohibits the approval of the application if the applicant has unlawful immigration status on the date of filing.

The relevant TPS statute, INA 244a(f)(4) (8 U.S.C. §1254a(f)(4)), states as follows:

During a period in which an alien is granted temporary protected status under this section- […] for purposes of adjustment of status under section 1255 of this title and change of status under section 1258 of this title, the alien shall be considered as being in, and maintaining, lawful status as a nonimmigrant.

The argument advanced by DHS, and accepted by the lower court, was that INA 245 requires both a prior admission and a valid status at the time of filing, and that the language in INA 244a(f)(4) is targeted at this latter requirement; a person with TPS is considered to have lawful nonimmigrant status, but nothing in the statute requires that they be treated as if they were admitted.

I think Sanchez was probably screwed no matter what, but I also think that his counsel could have advanced more persuasive arguments. Their primary argument was that there is an indissoluble relationship between admission and nonimmigrant status; that an understanding of the INA supports the point of view that anyone who has nonimmigrant status should be considered (for all purposes, and not just INA 245) to have been admitted. The Court noted that U status is an exception: a person who enters the United States without inspection, but is the victim of certain serious crimes, may apply for, and be granted U nonimmigrant status notwithstanding the fact that they weren’t admitted. So it’s no surprise that all nine justices found that the plaintiffs’ argument falls apart (and not only were there no dissents, but there were no concurring opinions either!): not all noncitizens who have nonimmigrant status under INA 101(a) are admitted; and therefore there’s no basis to say that the constructive nonimmigrant status granted by INA 244a(f)(4) entails an admission, either.

To me, there is a different, stronger argument that maybe, at least, Sotomayor and Breyer would have accepted. Sanchez still would have lost 7–2 or worse, but it’s interesting to think about. My argument is that if you look at the INA, you see that in general there’s a lot of sloppy drafting, where Congress, by writing an alien admitted under section X or similar, really means an alien who holds X status.

A great example of this is INA 245(l), which allows a nonimmigrant admitted into the United States under section 1101(a)(15)(T)(i) to adjust status. However, if going by the literal definition of admitted, then no one can possibly qualify for this, because it’s impossible to be inspected by CBP and granted admission in T-1 status. T-1 status is only granted to people who can demonstrate that they are in the United States on account of being a severe form of human trafficking. If CBP granted someone admission in T-1 status, then they would basically be giving the traffickers free rein to bring that person into the US. To have T-1 status, one of two things must happen: the traffickers must have smuggled you into the US, or you must have been coerced by the traffickers into entering the US in some legal manner (such as using a B-2 visa), after which you made your claim for T-1 status. Now, Congress obviously didn’t literally mean you must have been admitted in T-1 status in order to qualify under INA 245(l), since that would apply to nobody. Nor is it reasonable to interpret 245(l) as permitting adjustment only for people who were literally admitted into the US, and now hold T-1 status. That would yield an absurd result: people who were kidnapped and smuggled into the US by traffickers wouldn’t be able to benefit from 245(l).

It’s clear that when Congress wrote 245(l) (and we can find many other parts of the INA that were written similarly), the admitted wording was not meant to denote literal admission, but rather, the granting of the relevant nonimmigrant status. Congress did, in some cases, use more precise wording such as an alien admitted (or otherwise provided status) …. This reflects the fact that the different parts of the INA were not all written by the same congresspeople, and some of them (or their staffers, at least) are more precise than others.

Since Congress routinely conflates admission with the granting of nonimmigrant status, it would be reasonable to assume that, except where explicitly stated otherwise, any grant of nonimmigrant status is an admission. This is the obvious way to make 245(l) and other parts of the INA make sense.

To be clear, the Third Circuit did already reject this argument, citing In re H-G-G-, 27 I. &N. Dec. 617, 635 (AAO 2019) (citing In re V-X-, 26 I. &N. Dec. 147 (BIA 2013)), which found that a grant of asylum is not an admission. I believe that this precedent should also be overturned; a grant of asylum is also an admission (though not as a nonimmigrant, certainly). In re V-X- acknowledged that a grant of adjustment of status is an admission: for example, if a person had entered the United States without inspection but managed to get a green card (whether through asylum, the Cuban Adjustment Act, U status, or some other route) then the BIA would consider them admitted as of the date LPR status is granted. This is because, in their words, declining to consider adjustment of status as an “admission” would result in bizarre and absurd consequences, among them being the fact that “many lawful permanent residents would be considered inadmissible, despite their lawful status, based on their presence in the United States without having been admitted. (citing Matter of Alyazji, 25 I&N Dec. at 399). In In re V-X-, the BIA argues that no similar absurdities occur when they decline to also consider a grant of asylum to be an admission. I disagree! For example, INA 212(a)(9)(B) penalizes noncitizens who have been unlawfully present in the United States for 180 days or more, where the class of unlawfuly present noncitizens includes those who are present in the United States without being admitted or paroled. There is an exception for periods of time in which an alien has a bona fide application for asylum pending. It’s obvious that once the person’s asylum application is granted and the person has asylum status, they are no longer unlawfully present; it would indeed be bizarre and absurd to say that they are lawfully present while their application is pending, but not after it is approved. And yet there is no explicit language in the INA that says that a person (who entered without inspection) granted asylum is not unlawfully present, unless we consider that person to be admitted by such grant. To be clear, in most cases, this doesn’t matter; the asylee will adjust to permanent resident status, and 212(a)(9)(B)(i) will cease to apply to them. However, if the asylee, for example, married a Canadian citizen, relocated to Canada, and eventually became a Canadian citizen, it would be bizarre and absurd if they were banned from visiting the US on account of having once been an asylee, who was not admitted to the United States, and was therefore considered unlawfully present while an asylee.

We can also apply this reasoning to the case of U status that the Court discussed. A person might have entered the United States without inspection and then obtained U status, and then left the US after the inspection was complete; USCIS policy is that anyone in nonimmigrant status (including U status) is not accruing unlawful presence. Yet again, looking at 212(a)(9)(B)(ii), unlawful presence includes being present without admission or parole. USCIS policy here (which is just common sense; a person who has valid status cannot be said to be unlawfully present) can again be squared with the statute by considering the grant of U status to be an admission.

It should be so for TPS as well. Any grant of LPR status, nonimmigrant status, asylum, TPS, or any other kind of status authorized by Congress, to a person who was not already admitted to the United States, should be considered an admission, because this is required in order to make sense of the INA.

Finally, I also reject the argument raised by the defense (and accepted by the Court) that if a grant of nonimmigrant status were automatically an admission, then the inspected and admitted or paroled requirement of INA 245(a) would be superfluous. The reason why it is not superfluous is that some kinds of 245(a) applicants don’t need to have valid status at the time of filing: for example, immediate relatives of US citizens. We may draw an analogy with the following hypothetical Narnian nationality law:

A person who, at the time of their birth, has at least 1 parent who is a Narnian citizen is a Narnian citizen at birth if:

• Both of their parents are Narnian citizens at the time of the person’s birth; or
• The person is born in Narnia; or
• The person would otherwise be stateless at the time of their birth.

This is a perfectly reasonable way to write the law: anyone claiming Narnian citizenship through this paragraph must satisfy the requirement to have one Narnian citizen parent, and at least one additional criterion. One of those possible criteria, namely having two Narnian citizen parents, clearly implies the threshold requirement of having one Narnian citizen parent. But there are other possible criteria which don’t; therefore, none of the words in this paragraph are superfluous.

It is the same with INA 245(a) and (c): the condition of being admitted or paroled in INA 245(a) is analogous to the requirement to have 1 Narnian citizen parent. The additional conditions in INA 245(c) are analogous to the following additional criteria: either you must have valid status at the time of filing (which implies having been admitted or paroled, the way that having 2 Narnian citizen parents implies having 1 Narnian citizen parent), or you must be an immediate relative of a US citizen. (I have simplified the statute a lot here; there are other requirements and criteria as well.)

In conclusion, having valid status (including status that was granted after entry, in the case of a person who entered without inspection) should be considered an admission (except in the case of parole); this is necessary to make sense of the INA, and it does not render INA 245(a) superfluous. Therefore, TPS holders should be considered to satisfy the requirement of INA 245(a).

US Citizenship Act of 2021 – key provisions

Sen. Menendez released the text of the U.S. Citizenship Act yesterday (the bill that Biden claimed to have sent to Congress on day one, i.e. Jan 20). It’s 353 pages long, so I’m only going to summarize some key provisions that are likely to be of most interest to people who have previously read my US immigration-related writing. The bill is quite ambitious, and therefore highly unlikely to pass the Senate in its current form (some doubt that it can even pass the House). However, it sets a starting point for negotiations and perhaps a watered-down version can eventually pass (though I wouldn’t hold my breath if I were you).

Title I, Subtitle A: New paths to lawful permanent resident status

• Allows DREAMers to apply for lawful permanent resident (LPR) status, i.e., a green card, if they meet one of the following conditions:
  • earned a diploma from a US high school; or
  • earned a degree from a US college; or
  • completed at least two years of a degree program in the US; or
  • served in the US armed forces for at least 2 years; or
  • have been gainfully employed for at least 3 years, but enrollment in a post-secondary institution also counts toward the 3 year requirement.
• Allows citizens of TPS and DED designated countries to directly apply for LPR status if they have resided continuously in the US since January 1, 2017.
• Allows agricultural workers to directly apply for LPR status if they performed agricultural labor or services for at least 2,300 hours or 400 work days during the 5 years immediately preceding such application.
• Creates a new status called “Lawful Prospective Immigrant”. This is not LPR status, but is a transitional status that an immigrant can apply for if they do not fall into one of the above categories.
  • This status lasts 6 years and can be renewed.
  • Allows the holder to work and travel on basically the same terms as a lawful permanent resident (green card holder).
  • Can be converted into LPR status after 5 years.
  • To apply, you must be unlawfully present, unless you have H-2A status or you have worked in essential infrastructure during the COVID-19 pandemic. More on this in the comments.
• Limits the above provisions to individuals who were present in the US on Jan 1, 2021. However, exceptions can be granted for humanitarian, family unity, or other public interest purposes in the case of individuals who were removed during the Trump administration, if certain other conditions are met.
• Individuals may not qualify for the above benefits if:
  • they are inadmissible due to criminal convictions under the current standards (INA 212(a)(2)), or
  • they have been convicted of any felony, or
  • they have been convicted of 3 or more misdemeanors (not including simple possession of cannabis and minor traffic offenses)
  • Felony and misdemeanor convictions are not disqualifying if they include the person’s immigration status as an “essential element”. In other words, they are only disqualifying if they would also have been crimes if they had been committed by a US citizen. For example, presumably, a conviction for “possessing a firearm while an unauthorized immigrant” would not be disqualifying.
  • There are waivers available for the above grounds of ineligibility, which I won’t get into here.
• Individuals may qualify for the above benefits notwithstanding:
  • public health grounds of inadmissibility (INA 212(a)(1)),
  • likelihood of becoming a public charge (INA 212(a)(4)), and
  • most kinds of previous immigration violations, including overstaying, illegal entry, fraud or misrepresentation in connection with immigration applications, false claims to US citizenship, or having voted while not a citizen.
• Individuals who are in removal proceedings must be given an opportunity to apply for the benefits of this subtitle before being finally removed.
• Spouses and children of individuals who qualify for the above immigration benefits may derive immigration benefits through the principal applicant, without having to meet the qualifications themselves. For example, an undocumented spouse of an agricultural worker could obtain LPR status without needing to themselves be an agricultural worker.

Title I, Subtitle B: Miscellaneous reforms

• Reinstates the V visa program, which allows people who are waiting in line for a family-based immigrant visa to live and work in the US while waiting in line.
• Allows individuals to qualify for immigration benefits if their criminal convictions have been expunged or if the court has issued a judicial recommendation against removal.
• Expands availability of humanitarian, family unity, and public interest waivers of grounds of inadmissibility. (Grounds of inadmissibility based on national security cannot be waived.)
• Allows deportation to be waived for humanitarian, family unity, or public interest reasons. (This does not apply to individuals who have committed an aggravated felony or who must be deported for national security reasons.)
• Waives the 5-year waiting period for LPRs to apply for citizenship, if the LPR was lawfully present in the US and eligible for employment authorization for at least 3 years before becoming an LPR.
  • Reporters and immigration lawyers seem to assume that eligible individuals will still have to wait 3 years after becoming an LPR before they can apply for citizenship. This would also align with VP Harris’s comments that the bill would create an 8 year path to citizenship (5 years as LPI + 3 years as LPR). However, the actual text, at least the version above, doesn’t have the 3 year waiting period. The bill may be amended later to bring the text in line with the intent.
  • Lawful Prospective Immigrants will be considered lawfully present. Therefore, individuals who qualify for LPI status will (under the current wording) have a 5-year path to citizenship, by obtaining LPI status, adjusting to LPR status after 5 years, then immediately applying for naturalization on the basis of their previous LPI status. If the text is amended to reinstate the 3 year waiting period, then it will be a 8-year path.
  • DREAMers will have a 5-year path to citizenship, since they could apply for LPR status immediately, and then have the ordinary 5-year waiting period as an LPR before applying for citizenship.
  • This provision would also apply to many employment-based immigrants, since many of them worked in a status such as H-1B or L-1 for several years prior to becoming an LPR.

Title II: Border reforms

• Subtitle A is titled “Promoting the Rule of Law, Security, and Economic Development in Central America”. It appears to be focused on forming partnerships with Central American countries to help improve the conditions of those countries so that fewer people will irregularly migrate to the US. I’ll skip the details of this subtitle, but it’s worth noting its existence.
• Subtitle B is about improving refugee processing. It does not increase the refugee cap as it currently exists in law, but codifies into law the former Central American Minors Program, exempting certain Central American minors from the refugee cap if they have a parent who is lawfully present in the US, and introduces a new Central American Family Reunification Parole Program, which allows certain Central Americans to be paroled into the US if they are waiting in a family-based immigration backlog.
• Subtitle C is focused on improving screening of legitimate trade and travel across the border and enhancing the ability to detect contraband, especially illegal drugs, including by deployment of additional technology along the border.
• Subtitle D prohibits punitive family separation policies and destruction of DHS records relating to detained children. It also directs government officials to set appropriate standards of care related to detained individuals, but without going into any specifics.

Title III, Subtitle A: Immigrant visa reform

• Stops counting immediate relative visas against the family-based visa quota. (Currently, there is no limit on immediate relative visas, e.g., spouses of US citizens, but the number of such visas issued is deducted from the family-based quota.) This will ensure that at least 480,000 non-immediate-relative family-based visas will be available per year, compared to the current system which only makes 226,000 non-immediate-relative family-based visas available per year.
• Improves visa recapture for family-based immigrants. In addition to the base number of 480,000 visas per year, there will also be extra family-based visas equal to the number of unused employment-based visas from the previous year, plus the number of unused family-based visas from fiscal years 1992 through 2020.
• Increases the base quota for employment-based immigrants from 140,000 to 170,000. (However, see Subtitle D.)
• Recaptures unused employment-based visas from fiscal years 1992 through 2020. These will be added to the employment-based quota. (The current system recaptures unused family-based visas from the previous year under the employment-based category, but does not recapture older unused employment-based visas. The new system would do both, which would have a substantial impact on reducing backlogs.)
• Reclassifies spouses and children under 21 of LPRs as immediate relatives, thus exempting them from quotas.
• Under the new system, no more than 20% of the total family-sponsored visas per year could go to natives of any single country. (Under the current system, the limit is 7%, which creates extremely long backlogs for Mexicans. This should alleviate this issue somewhat, although it’s not clear how much.)
• Priority dates from any kind of family-sponsored or employment-sponsored immigrant petition can be ported to any subsequent petition, even if it’s in a different category.
• The 3-year bar and 10-year bars, which currently prohibit people from entering the US for a period of time if they were previously unlawfully present in the US, are repealed.
• The permanent bar is repealed. (The permanent bar results in a lifetime ban from entering the US, if a person either was unlawfully present for 1 year or was deported, and then subsequently enters the US illegally.)
• The 5-year, 10-year, and 20-year bars on the return of individuals who were previously deported are maintained, but the Secretary of Homeland Security is given broad discretion to waive these bars for both nonimmigrants and immigrants.
• US citizen parents can transmit their citizenship to adopted children on the same basis as naturally born children who are born outside the US, if the adoption occurs before the age of 1 year. Such adopted children would be considered to have US citizenship from birth. (Don’t ask me if they can run for president when they turn 35. I don’t know.)
• Children born to parents using assisted reproductive technology would be able to derive US citizenship from their parents on the same basis as naturally born children.

Title III, Subtitle B: NO BAN

• Expands the current non-discrimination provisions in order to include religion as a protected trait.
• Expands the current non-discrimination provisions so that they apply to applicants for any kind of visa, admission to the United States, and any kind of immigration benefit.
• Limits INA 212(f) (which President Trump, and more recently Biden, used to enact immigration bans) so that it can only be used for grounds of “security or public safety of the United States, or the preservation of human rights, democratic processes or institutions, or international stability”. This would bring permissible uses of presidential bans in line with how the authority was typically used before Trump.
• Explicitly clarifies that 212(f) is subject to the non-discrimination provisions (see my comments below).
• Adds a “rule of construction” paragraph that prohibits 212(f) from being used “in a manner inconsistent with the policy decisions expressed in the immigration laws.”
  • Presumably, this is intended to prevent situations like Trump’s work visa ban, where he banned entry of entire work visa categories on economic grounds, despite the fact that Congress had already established a procedure for preventing work visas from being used in ways that would harm US citizen workers. However, I am not sure whether it is explicit enough to prevent other similar bans from being enacted by future presidents.

Title III, Subtitle C

• Increases the annual number of diversity immigrant visas from 55,000 to 80,000.

Title III, Subtitle D: Employment-based immigration reforms

• Immigrants who have earned a STEM PhD from an accredited US institution would be exempt from quotas. The text is not clear on what the process would be for them to obtain a green card, but as written, they would be exempt from the labor certification requirements of INA 212(a)(5), and therefore presumably would not be required to have a job offer lined up. It seems likely that regulations would establish a simple self-petitioning process, similar to the EB2-NIW self-petition but without any requirement to demonstrate exceptional ability.
• Immigrants who have had an immigrant visa petition (such as an I-130 or I-140) approved for over 10 years would be able to obtain a green card or immigrant visa notwithstanding the fact that their priority date may still not be current.
• Spouses and children of family-based, employment-based, and diversity immigrants would no longer consume quota. (For employment-based immigrants, the effect of this provision would be similar to doubling the quota, since USCIS data shows that principal employment-based applicants have about 1 dependent on average.)
• Abolishes the 7% per-country rule for employment-based immigrants.
• Abolishes the CSPA offset. (This subsection seems like a gesture of goodwill toward Chinese immigrants, but actually has no effect. The CSPA offset expired at the end of fiscal year 2020. If they really want to make a gesture of goodwill, they should recapture the visas that were used for the offset.)
• The extra 30,000 EB visas per year would be allocated to the “Other Workers” category. There would be no increase in the base EB1 and EB2 quotas (however, see the recapture provisions mentioned in Subtitle A).
• Sec. of Homeland Security is given the authority to establish a procedure for temporarily reducing EB2 and EB3 visas due to domestic unemployment. (There’s absolutely no way this provision will be abused, no siree…)
• A new pool of 10,000 EB visas would be created that would be distributed to cities and counties, which would be able to allocate them based on local needs. This pilot program would sunset after 5 years.
• Allows, but does not require, the H-1B selection process to take into account wages (as opposed to being a random lottery as is currently done).
• Makes F-1 students eligible for dual intent (i.e., they may receive visas even if their intent is to eventually apply for permanent status in the US), provided that they are pursuing a full course of study at an institution of higher education.
• H-4 children who first obtained H-4 status before the age of 18 will be able to continue in H-4 status after the age of 21, and will remain eligible to be derivatives on their parent’s green card application.
• Both H-4 spouses and H-4 children will be granted employment authorization explicitly by statute.
• The AC21 H-1B extension provisions for lengthy adjudications will be expanded to also include F-1, L-1, and O-1 non-citizens. That is, any F-1, H-1B, L-1, or O-1 non-citizen will be able to file to extend their status, if a labor certification or an employment-based immigrant petition was filed at least 1 year prior to the extension application. This extension will be for 1 year, and will be indefinitely renewable until the non-citizen’s lawful permanent residence is approved or denied. Furthermore, during each such 1-year extension, the non-citizen will be granted unrestricted employment authorization. This is especially important for F-1 non-citizens. They will be able to go on OPT, get sponsored for a green card at least 1 year before the OPT is to expire, and then (in effect) extend their OPT for as long as necessary to obtain the green card. It will not be necessary for them to enter the H-1B lottery and take a lottery slot away from someone else who is applying from outside the US.

Title IV

• Orders the Attorney General to appoint more immigration judges, for the purpose of reducing immigration court backlogs.
• Requires the government to expeditiously provide people who are in removal proceedings with a copy of their immigration file that is maintained by DHS (this is currently only available through a time-consuming FOIA request).
• Requires the government to provide counsel to individuals in removal proceedings who cannot afford counsel.
• Eliminates the 1 year time limit for non-citizens to apply for asylum after entering the US.

Title V: Employment authorization

• Expands eligibility for U status to noncitizens who have suffered severe harm due to labor and employment law violations.
• Prohibits removal of victims of labor and employment law violations until a decision on their U status application has been made.
• Noncitizens who worked without authorization and whose employers illegally withheld wages will be entitled to back pay (overruling the 2002 Supreme Court decision in Hoffman Plastic Compounds, Inc. v. NLRB).
• Prohibits discrimination against noncitizens in hiring. Presumably this does not mean employers are required to hire noncitizens who require sponsorship, but in the case of noncitizens who do not require sponsorship, such as OPT EAD or H-4 EAD holders, they must be considered for employment on the same terms as LPRs. However, employers can still prefer a citizen over an equally qualified noncitizen.

My comments

• The adjustment of status provisions for DREAMers are very ambitious. If something like them do make it into the final law, it’s likely that Republican support would be conditioned on imposing waiting periods (most likely in the form of a “back of the line” provision, i.e., they would not get green cards until everyone who is in line for an immigrant visa has had the opportunity to receive one).
• It seems unlikely that the general Lawful Prospective Immigrant pathway will make it into law, if Republican support is required to pass the bill. To have a chance at getting Republican support, it would probably have to be severely limited (e.g., to individuals who have resided in the US for 10+ years prior to the enactment of the Act).
• The waiver provision for the 5 year waiting period for US citizenship would benefit me and other people who were stuck in employment-based immigration backlogs while working in the US (mostly Chinese and Indians). I’m quite pleasantly surprised that the Democrats put this in the bill and didn’t limit it to just DREAMers.
• The Central American Minors Program and Central American Family Reunification Parole Program seem unlikely to get any Republican support, for obvious reasons, even when paired with the other reforms in Title II.
• The proposed expansion of family-based immigration is massive. It would increase the number of family-based visas issued without taking visas away from anywhere else. Notably, parents of US citizens would continue to be eligible for immediate relative status (exemption from quotas) under this bill. Adult children and siblings of US citizens would continue to be eligible for family-based immigrant visas. This is an ambitious bill. It is not about making compromises to appease Republicans who are concerned about too much immigration. Of course, this means the odds of Republican support for such provisions are basically zero. If family-based immigration reform is to get any support from Republicans, it will have to be something more like the 2013 Gang of Eight bill, which eliminated immigrant visas for parents and siblings of US citizens, and limited eligibility for adult children of US citizens.
• The increase in diversity visas will not get any Republican support.
• The NO BAN provisions should be regarded as the bare bare minimum that we should demand from Democrats. If they can’t pass it as part of this comprehensive bill, they should pass it as a standalone bill. As a human being, I feel that Trump’s abuse of the law (and the fact that the Supreme Court allowed him to get away with it) to ban entire countries from immigrating is despicable and must never happen again. As a Chinese person, I fear that if the law is not changed to prevent it, then future president Cotton will use it to ban virtually all Chinese people from immigrating to the US. If the Democratic Party does not manage to even fix this issue with the law, they are really and truly useless, and I see no reason why I should vote for them if/when I become a citizen.
• I was worried about whether the NO BAN provisions were going to be explicit enough. Remember that in the Hawaii case, the Supreme Court ruled that—even though the law already says quite explicitly that discrimination based on nationality is not permitted in the immigrant visa issuance process—Trump can still ban immigrants based on nationality. Their logic was that the existing nondiscrimination provisions only apply to people who are admissible in the first place, and Trump can make people inadmissible based on nationality using 212(f), which prevents them from benefitting from the nondiscrimination provisions. Thankfully, the proposed language in the new bill explicitly states that uses of 212(f) shall comply with 202(a)(1)(A) (the non-discrimination provision).
• The employment-based immigrant visa reform provisions seem like they could get bipartisan support. However, assuming that the entire bill doesn’t get passed (which seems extremely likely), I have no idea whether the Democrats will break out these provisions into a standalone bill. As everyone knows, Democrats do not particularly care about employment-based immigrants.
• Notably, the bill does not include any provisions for a points-based system for allocation of employment-based immigrant visas. This is disappointing, and means that prospective employment-based immigrants will continue to struggle with the issue of having to maintain employer sponsorship and remain in certain fields of employment in which obtaining sponsorship is relatively easy (such as software engineering). I’m a software engineer but I don’t think it’s healthy for a country to have an immigration system where it’s really hard for workers who aren’t software engineers to get green cards.
• The F-1 dual intent provision is nice, but it doesn’t go far enough. Congress should abolish the single intent policy in general. Anyone who meets the qualifications for a nonimmigrant visa should be able to receive one notwithstanding the fact that they may eventually seek permanent residence, as long as they are not planning to use the nonimmigrant visa as a backdoor to illegally reside in the US. (Canada, which accepts a large number of immigrants per year but strictly enforces its immigration laws, permits dual intent for all visa categories.)
• As some lawyers I follow on Twitter point out, appointing more immigration judges is not a sustainable solution to deal with immigration court backlogs. What we really need is to expand legal avenues to remove cases from the backlog (i.e., instead of having hearings on whether to deport certain people, they should just not deport most of them). But maybe that’s too extreme to be considered right now.
• A number of other provisions that would have been nice to have did not make it into the bill:
  • Strengthening access to employment authorization documents (EADs) by requiring USCIS to issue EADs within a specified time frame, or allowing more types of documents to be used as proof of employment authorization, for example, allowing an I-94 evidencing H-4 status to be used for I-9 purposes, so that a future administration cannot kill H-4 employment authorization by taking forever to issue EADs, which was done by the Trump administration.
  • Strengthening and explicitly protecting the current (c)(9) EAD rule, which allows noncitizens who are waiting for an adjustment of status application to be processed to work before their green card is finally issued. Congress should codify this rule into law to ensure that it is not rescinded by a future president (Trump was reportedly considering such a move, but I guess it was too extreme even for him) and ensure that applicants are not plagued by lengthy delays.
  • Narrowing discretionary bars to asylum. The current law basically allows the administration to make up whatever “discretionary” criteria they want in order to restrict who may qualify for asylum, which was abused by the Trump administration to make it almost impossible to qualify and also to impose a bunch of random criteria with no real connection with anything intended by Congres. For example, one of Trump’s proposed rules (which was halted by a federal judge before it was to take effect) would have made unlawful entry and the use of fraudulent documents a negative discretionary factor (meaning that it would count against you in terms of whether you qualify for asylum, even if you meet the definition of a refugee). This makes it very difficult to escape from persecution because most people who need to flee from persecution would never be able to get a visa legally. It also would have denials mandatory in the case of an asylum applicant who has ever filed their tax return late or failed to report all income, which seems to have no purpose other than further disqualifying a bunch of people. Congress should mandate that the exercise of negative discretion be limited to individuals who have committed a serious crime, are a threat to public safety, or have third country options available to them. People who are genuinely fleeing from persecution should never be denied asylum on the basis of immigration violations alone or illegal acts that most people would only get a slap on the wrist for. Although Trump’s rule was put on hold by courts, the law should be revised so that there is not even a semblance of lawful authority of the President and executive officials to enact similar regulations in the future.
  • The F-1 OPT program should be codified into law to ensure that it cannot be rescinded by executive action. While even Trump did not rescind or even limit F-1 OPT, it’s possible that he would have tried to do so in a second term. Plus, Trump was arguably not even a true believer in immigration restrictionism—he just did certain things in order to satisfy his base. What if he had been one?
  • Existing DHS policy is that if you file for an extension of status while your current status is still valid, but then your current status expires while you’re waiting for the extension of status to be processed, then you won’t be deported or considered as unlawfully present unless and until the extension is denied. While it’s unlikely that this policy will be rescinded by a future administration, I would rest easier if it were explicitly codified into law.
  • There should be a general grace period for anyone who is suddenly and unexpectedly required to leave the US, or example an F-1 student whose OPT application is denied. Under current policy, they are required to leave the US immediately upon the denial, but DHS will give them some (unknown) reasonable amount of time to depart before trying to deport them. I would rest easier if there were an explicit grace period in the statute.
  • Reinstating the visa revalidation provision, which would allow certain people such as H-1B workers to renew their visas without leaving the US. (The purpose of this would be to ensure that, if they needed to travel at a later date, they would not get stuck outside the US waiting for an opportunity to renew their visas before being able to return.)
  • Reforming INA 221(i) so that the Secretary of State cannot revoke visas for arbitrary reasons and individuals whose visas have been so revoked cannot be deported on the basis of the revocation. Visa revocations should be limited to those individuals who should not have been eligible for the visa in the first place, or who have since become ineligible or a visa. Deportations should be limited to those individuals who obtained their visa fraudulently or have committed a deportable offense; individuals should not be deported just because their visa was revoked on the grounds that they may not qualify for a visa in the future.
  • There should be a provision that allows people who were not able to receive a visa or be admitted to the United States on the basis of Trump’s immigration bans (which Biden, infuriatingly, has left in place) to enter the US once the bans are over. This is especially important for diversity lottery winners, since they cannot just get back in line the way that family-based and employment-based immigrants can.

Further comments on LPI status

The text makes individuals ineligible for LPI status if they are a foreign goverment official in A status (8 USC §1101(a)(15)(A)). This is clearly a typo, since it has an exemption for H-2A noncitizens (you cannot be in both A status and H-2A status at the same time). It seems obvious that they meant to refer to 8 USC §1101(a)(15), and not to subparagraph (A) in particular. In other words, if you have lawful nonimmigrant status, you cannot apply for LPI status. The absurdity of such provision is always pointed out every time they are proposed: why do Democrats want to punish people who followed the law?

There are basically two arguments. There’s a specious legalistic argument, and the real one. The specious legalistic argument is that people who come here on nonimmigrant visas agree to depart at the end of their period of authorized stay. For example, F-1 visa holders agree that they will depart once their studies and any authorized period of practical training have concluded (though they can, of course, “change their minds” later and apply for some other status to remain in the US). On the other hand, people who crossed the border without inspection did not enter into any such agreement. So, according to this argument, people who are in lawful nonimmigrant status have previously “waived” their right to participate in legalization programs in exchange for the benefits of being in lawful status during their stay in the US. I’m sure most people don’t actually find this argument convincing, especially since someone would still be eligible for legalization if they entered on a valid visitor visa and they just decided to overstay for a few months (with their status having become unlawful prior to Jan 1, 2021).

The presumed real reason why (most) lawful nonimmigrants are never included in proposed legalization provisions is that legalization is always meant to be a one time solution to address the large undocumented population of the United States—which both parties agree is a problem that needs to be solved one way or another, and hope to prevent from happening again—whereas it doesn’t make sense to create a one time special path to citizenship that e.g. the 1 million lawful international students who were in the US on Jan 1, 2021 can benefit from but which future international students will not be able to benefit from. (What’s so special about those ones in particular?) And stapling a green card to the diploma of every international student, now and in the future, is not a realistic proposal, as much as open borders people like me want it to be. It makes even less sense to give everyone who happened to be visiting the US on Jan 1, 2021 a special path to citizenship.

Still, limiting eligibility to people who lack lawful status just doesn’t sit right with me. But I don’t know what a politically viable alternative would be. Republicans may very well force a compromise where legalization applicants go to the back of the line, but it still wouldn’t change the fact that they would be receiving a special opportunity that the F-1 students and lawful temporary workers would not (since not every international student or temporary worker has a path to citizenship, and that will continue to be the case even if the bill is passed).

How exactly to do linear time quickselect with duplicate elements?

It’s well known that the quickselect algorithm, which runs in average case linear time, can be made linear time in the worst case as well, by using the median of medians strategy to select the pivot. This also allows us to implement quicksort in guaranteed time.

While median-of-medians is theoretically interesting, it is not of much use in the real world. For sorting, the introsort approach with median-of-three partitioning is more suitable. Median-of-three partitioning has low overhead, and unlikely to degenerate to quadratic time behaviour except in the case of unusual adversarial sequences. On those rare occasions when the recursion gets too deep, introsort switches from quicksort to heapsort. Median-of-medians partitioning has too much overhead compared to heapsort to actually be useful. For selection, libstdc++ pursues a similar approach, namely median-of-three partitioning and switching from quickselect to heapselect if the recursion gets too deep; this implies that the selection may take time in rare situations, which is unlikely to cause any practical issues. Interestingly, libc++‘s std::nth_element implementation simply degenerates to quadratic time when given a median-of-three killer sequence as input (Musser, 1997). Presumably, few people complain since such sequences rarely occur in practice, and this is perfectly kosher according to the C++ standard, which merely requires linear time performance on average.

Why might one be interested in worst-case linear time quickselect despite the fact that it’s not useful enough to have made it into the two most widely used and respected C++ standard library implementations? The main reason I can think of is that you might, at some point, be applying for a job, and you might get an annoying interviewer who will dock marks from you if you don’t write a solution that has asymptotically optimal worst-case performance. You might say to yourself, I wouldn’t want to work for a company with this kind of interview process anyway. If that’s the case, I suppose there’s no compelling reason for you to read the rest of this post, other than curiosity.

When all elements are distinct, quickselect with median-of-medians is not hard to implement. The particular way in which the partitioning loop is implemented is immaterial, since there is only a single correct result. For example, we might use the simple Lomuto partitioning procedure given in CLRS. However, the version in CLRS takes the rightmost element of the range as the pivot, and CLRS itself remarks that the procedure needs to be modified to take an explicit pivot element in order to be usable with the median of medians. Of course, we can simply swap this element with the rightmost element and proceed with the original procedure:

// let x = *pivot; then, after this call, [begin, result) <= x && *result == x && (result, end) > x
template <std::random_access_iterator It>
It partition(It begin, It pivot, It end) {
    using std::ranges::iter_swap;
    iter_swap(pivot, end - 1);
    It result = begin;
    for (It i = begin; i < end - 1; i++) {
        if (*i <= end[-1]) {  // NB: end[-1] is where the pivot value is right now
            iter_swap(i, result);
            ++result;
        }
    }
    iter_swap(result, end - 1);
    return result;
}

(This code requires some additional concepts beyond std::random_access_iterator, and should probably be rangified. This is left as an exercise for the reader.)

The full quickselect may look something like this:

template <std::random_access_iterator It>
void nth_element(It begin, It nth, It end) {
    const auto N = end - begin;
    
    if (N <= 5) {
        // insertion sort
        for (auto i = begin; i < end; i++) {
            const auto dest = std::upper_bound(begin, i, *i);
            std::rotate(dest, i, i + 1);
        }
        return;
    }
    
    for (int i = 0; i + 5 <= N; i += 5) {
        // move the median of this block of 5 into the middle of the block
        nth_element(begin + i, begin + (i + 2), begin + (i + 5));
        // move the median to the beginning of the array
        std::ranges::iter_swap(begin + (i / 5), begin + i + 2);
    }
    nth_element(begin, begin + (N / 10), begin + (N / 5));
    
    const auto m = partition(begin, begin + (N / 10), end);
    
    if (nth < m) {
        nth_element(begin, nth, m);
    } else if (nth > m) {
        nth_element(m, nth, end);
    }
    // if nth == m: nothing to do
}

Before we address the issue of duplicate elements, we should review the reason why this algorithm runs in guaranteed linear time. Let denote the worst-case running time of quickselect with median-of-medians partitioning, run on an array with elements. There are approximately groups of 5. The median of medians is greater than half of these medians (constituting approximately elements). Each of those medians is greater than two elements in its group of 5; thus, the median of medians is greater than approximately elements. By the same token, the median of medians is less than approximately elements. It therefore follows that the side of the partition we descend into has size at most approximately . The time to compute the median of medians itself is , and the partitioning step is of course linear. Thus

where we have used to make our use of approximately precise, since e.g., . Now, because is strictly less than , it follows that . A careful proof can be found in CLRS; you can also use the Akra–Bazzi theorem, which has the advantage that it lets us also easily answer the question of what happens if the two factors of 1/5 and 7/10 were replaced by factors whose sum is exactly 1, or strictly greater than 1. As you can probably guess, the answers would be and , respectively, where is a constant greater than 1.

With the partitioning procedure given above, we can immediately see that there will be a problem if duplicate elements are present. In particular, if all elements in the array are equal, the right half of the partition will always be empty, leaving us to recurse into the left half which has elements. In fact, because there is only one possible partition value, it doesn’t matter how we select that value; the running time will be at least quadratic, and the recursive nature of the median-of-medians computation actually results in superpolynomial time. It’s therefore clear that we must change the way we partition.

Indeed, the poor behaviour of Lomuto partitioning in an array where all (or almost all) elements are equal is a pretty good reason not to use it, even in the sorting case where we can switch to heapsort after a certain point. This switch-over would happen after recursive calls for some constant , meaning that by that time, operations have already been done, and nearly all of the array remains unsorted. It would be better, even for introsort, to use a partitioning procedure that behaves well in the presence of many duplicates. This is typically the Hoare partitioning procedure or a variant:

// let x be the initial value of *pivot and k the return value; then,
// [begin, k) <= x and [k, end) >= x
template <std::random_access_iterator It>
It partition(It begin, It pivot, It end) {
    using std::ranges::iter_swap;
    iter_swap(begin, pivot);
    It i = begin;
    It j = end;
    while (true) {
        do {
            --j;
        } while (*j > *pivot);
        while (*i < *pivot) {
            ++i;
        }
        if (i < j) {
            iter_swap(i, j);
            ++i;
        } else {
            return j + 1;
        }
    }
}

The Hoare partitioning procedure is more complex than Lomuto; it’s not immediately obvious, upon reading the code, that it’s even correct at all (this is an exercise in CLRS; solutions can be found online). Lomuto thus has pedagogical value, whereas Hoare is used in practice. In the case of all elements distinct, Lomuto generally performs many unnecessary swaps, since the kth element less than the pivot (in index order) will always get swapped into position k, even if its original position was fine (i.e., to the left of the pivot’s final position); Hoare does not do this, as every swap it performs (except for the initial swap to move the pivot to the front, which is necessary in order to avoid degenerate partitions) will have the effect of exchanging an element that should be on the left and is on the right with an element that should be on the right and is on the left. In the presence of duplicates, Hoare can perform some unnecessary swaps of an element equal to the pivot and on the left with an element equal to the pivot and on ther right. However, Lomuto will also perform unnecessary swaps here, and indeed, when all elements are equal, Lomuto will perform about swaps compared to Hoare’s .

A slight modification is needed to the nth_element implementation when using the two-way Hoare partitioning as shown above: the else branch must be made unconditional since the element at position m is not guaranteed to be in its final sorted position. With this change being made, our quickselect implementation should perform reasonably well in the presence of duplicates. But is it linear in the worst case?

The answer hinges on the issue of how lopsided a partition is possible in the presence of duplicates, where the pivot is chosen by median-of-medians partitioning. The case with all elements equal is actually a best case for Hoare partitioning; while it will perform unnecessary swaps, it will also move the left pointer in lockstep with the right pointer, meeting exactly in the middle. But what is a worst case? Well, if of the elements are zeroes, and are ones, and zero is chosen as the pivot (which is possible by gerrymandering), and the right pointer skips over all the ones at once and then moves in lockstep with the left, we’ll get a split where the left partition is about zeroes and the right partition has the remaining elements. Since , this is a sufficiently bad split to be problematic. However, this particular case isn’t actually possible, because in this case 0 wouldn’t be chosen as the partition anyway. If we gerrymander the array to make 0 the median of medians, but otherwise move the ones as far to the right as possible, it looks like 00011 00011 00011 … 11111 11111 11111 …, and Hoare partitioning will yield a 3:13 split in this case. Still, , greater than 1 by just a hair. Wait a second though—even this exact case is not possible, because we have written our quickselect above so that the medians all get moved to become the first elements of the array before the partitioning step is actually run. And even if a split worse than 1:4 can still happen, it’s not clear whether we can engineer the input so that the split is sufficiently bad upon every iteration, as the array gets reordered and whittled down, to yield superlinear running time. I don’t have an answer here; Hoare partitioning is difficult to analyze.

So what do we do? Well, you might feel that our algorithm by this point probably runs in worst-case linear time, and even if it doesn’t, it runs in time where is some small constant. But, as I said, you may be applying for a job where the interviewer wants you to write something that has provably worst-case linear time performance. In that case, it might occur to you that we need to be smart about how we handle elements that are equal to the pivot. (Duplicates that are unequal to the pivot are not a problem, since it is clear which half of the array they will end up in after partitioning.)

The solution to this problem is three-way partitioning: we must modify our approach so that the partitioning procedure is guaranteed to place all values equal to the pivot in their sorted positions. Writing such a partitioning loop is known as the Dutch national flag problem. There are various possible solutions; this one is based on (Dijkstra, 1976):

// returns the range of elements equal to the pivot.
// pivot is a value, not an iterator.
template <std::random_access_iterator It>
auto partition(It begin, It end, const auto& pivot) {
     using std::ranges::iter_swap;
     auto i = begin, j = begin, k = end;
     while (j < k) {
         const auto c = (*j <=> pivot);
         if (c == std::weak_ordering::less) {
             iter_swap(j++, i++);
         } else if (c == std::weak_ordering::greater) {
             iter_swap(j, --k);
         } else {
             j++;
         }
     }
     return std::ranges::subrange(i, j);
}

Why does this help? Well, the reasoning for why the median of medians is greater than at least elements when all elements are distinct carries over easily to the non-distinct case, but the inequality becomes non-strict: the median of medians is greater than or equal to at least elements and likewise less than or equal to at least elements. This implies that when the three-way partition is run on a range with elements, the returned range at least overlaps with the middle two-fifths of the array; this is a generalization of the case with all elements distinct, where the returned iterator would always fall within the middle two-fifths of the array. We amend the calling code thus:

const auto r = partition(begin, end, begin[N / 10]);
    
if (nth < r.begin()) {
    nth_element(begin, nth, r.begin());
} else if (nth >= r.end()) {
    nth_element(r.end(), nth, end);
}
// nth falls within r: nothing to do

Now, in each case where nth_element is recursively called, it cannot be with more than elements, since that would require the equal range to fall entirely within the elements at the other end, which cannot happen.

I haven’t measured the performance of the overall algorithm, but it’s clear that it suffers from more overhead than the case with all elements distinct (using Hoare partitioning) since, as with Lomuto partitioning, we may perform unnecessary swaps, wherein an element that is already in the correct region of the array (according to whether it is less than, equal to, or greater than the pivot value) is nevertheless moved to a different location. This overhead is incurred even if it turns out that there are no duplicates in the array after all. The overhead is made significantly greater if we do not have three-way comparisons available (or if we do not make use of them), as each element is then potentially subjected to two full comparisons: one to determine whether it is less than the pivot, and (if the answer is no) a subsequent one to determine whether it is equal. Such is the cost of writing a guaranteed linear time quickselect. It’s not hard to see why, in the real world, the libstdc++ approach is preferred: select the pivot using median-of-3, run Hoare partitioning (which will usually perform well in the presence of duplicates despite not checking for them explicitly), and then switch over to heapselect in the very rare cases where this fails to behave well.

More updates on immigrant visa spillover (why I don’t think 60,000 extra green cards will materialize)

In a previous post I discussed how a large number of family-based preference immigrant visas will not be used up by the end of the fiscal year and the unused visas will be added to the employment-based quota in the new fiscal year starting in October 2020 (next month), resulting in at least 200,000 employment-based green cards being available. I’m now convinced, however, that unless Trump loses the election, the vast majority of the extra green cards are not likely to be issued. And even if Biden takes over in January, he will likely have too much on his plate to prevent the visa wastage that Trump will set the system up for.

There are two specific mechanisms by which this visa wastage will occur. The first is the use of processing delays. USCIS announced that, while they had averted the furlough of 70% of their employees that was planned for August 30, there will be increased wait times across the board. Many observers don’t believe that USCIS had a genuine funding crisis in the first place—they manufactured it as cover for delaying the issuance of immigration benefits in general. And there have already been significant delays, as Charlie Oppenheim had indicated in a previous check-in that the EB quota would most likely not be hit in FY 2020. In other words, USCIS will not even issue an extra 16,253 EB green cards that are available in FY 2020 (total quota 156,253), so it seems foolish to expect them to use up the 60,000+ extra green cards that will be available in FY 2021. I’m not even sure if they’re going to issue the base number of 140,000 EB green cards in FY 2021.

The processing delays excuse is almost bulletproof. It may be that a House committee will eventually call Cuccinelli or Edlow to testify about the processing delays, but this is not likely to yield any relief as he can just reiterate the existing talking points regarding the delays and answer I don’t know regarding any specifics. The inquiry will end there; the House may be able to subpoena documents, but any real oversight can only be accomplished by forcing USCIS to generate detailed reports, which can only be done through legislation, not through a subpoena; and that will not happen as long as the Senate remains under Republican control. At risk of stating the obvious, the House also can’t pass any legislation by itself to force USCIS to speed up adjudications. One also shouldn’t pin any hopes on the other avenue for relief—namely, the courts—as the whole judicial process may take too long to and fail to prevent the visas from going wasted at the end of September 2021. This is particularly the case if the Supreme Court gets involved. So we find ourselves in a situation where there is ample motivation for the Trump administration to cause delays (for example, a recent Breitbart article encouraged him to do so in order to supposedly protect American workers) and little that can be done to stop them.

The other visa wastage mechanism is more obscure. It revolves around the question: how does the spillover actually get calculated and allocated (practically speaking)? The answer is as follows. Early in the fiscal year, the State Department estimates the quota for that fiscal year (in other words, they estimate the number of visas that have spilled over from the previous year, and add that to the base quota). In FY 2020, these estimates were published at some point in late October 2019 or early November (I don’t know the exact date). However, the September 2020 visa bulletin contains the following note:

The State Department is required to make the determination of the worldwide numerical limitations, as outlined in Section 201(c) and (d) of the INA, on an annual basis. These calculations are based in part on data provided by U.S. Citizen and Immigration Services (USCIS) regarding the number of immediate relative adjustments in the preceding year and the number of aliens paroled into the United States under Section 212(d)(5) in the second preceding year. Without this information, it is impossible to make an official determination of the annual limits. To avoid delays in processing while waiting for the USCIS data, the Visa Office (VO) bases allocations on the minimum annual limits outlined in Section 201 of the INA. On July 31st, USCIS provided the required data to VO.

In other words, it’s not until the final quarter of the fiscal year that USCIS transmits to DOS the data required to finalize the computation of the quotas. Until DOS receives that report from USCIS, they will simply assume that only the base quota (140,000 EB visas) will be available in that year, and move the cutoff dates accordingly. This implies that only at the very end of the year is USCIS able to approve more applicants using the spillover visas, based on the cutoff date advancements that were made possible by the spillover.

One might wonder why USCIS takes so long to provide the data. Is that also Trump’s fault? Interestingly, the answer is probably not. If you browse older visa bulletins from when Obama was in office, you see something similar—USCIS doesn’t send the report until July. This works fine in a typical year, when the amount of spillover visas is low. For example, the Sep 2016 visa bulletin gives the finalized EB quota for FY 2016 as 140,338, meaning that USCIS only then had to process 338 more EB adjustments in the last 2 months of the year than they would otherwise have had to. But in FY 2021, it’s simply not possible for USCIS to approve 60,000 extra applicants in the last 2 months (considering that in a normal year, only 35,000 applicants would be approved per quarter) regardless of who occupies the White House.

USCIS and DOS can work together to prevent the wastage by changing their procedures to accommodate the unprecedented amount of spillover in FY 2021. All they have to do is estimate very conservatively at the beginning of the fiscal year the number of extra EB visas; DOS can move the dates by taking into account those extra visas, and USCIS can approve them, and then in the last two months, the final number will be known and remaining visas can be issued (perhaps a small number more or less than was estimated to be available for those months). However, under the Trump administration, this isn’t likely to happen. It’s simply too easy for USCIS and DOS to just do what they’ve always done—knowing full well that it will lead to wastage—and pretend that the outcome couldn’t have been averted. Actively changing their procedures, even just a bit, in order to satisfy the Congressional mandate to use up all the visas would be seen as a massive giveaway to job-stealers like me.

As I mentioned before, I think that even if Biden takes over in January, it’s not likely that he’ll immediately take the necessary actions to prevent the visa wastage from unfolding. This doesn’t mean nothing will change if Democrats are elected; if Democrats can win the Senate as well as the Presidency, they could potentially increase both the EB and FB quotas for future years (and eliminate per-country caps). Trump staying in power, on the other hand, is unlikely (in my opinion) to be beneficial for EB immigrants the way that people sometimes think. Of course, I’m happy to be proven wrong—if lots of EB green cards get approved next year, it’ll be great to see them not go to waste and I’ll admit that some immigrants did benefit from Trump from Trump after all (while maintaining that it should not have been legal for Trump to use 212(f) to enact this travel ban in the first place).

Update on immigrant visa spillover

I previously wrote a post about the prospect of spillover of unused FB immigrant visas due to Trump’s immigrant visa ban to the EB quota. A lot of the information in that post was not accurate but I now have a better understanding of the situation so I am writing this update.

In a recent webinar with IIUSA (read a summary here), Charlie Oppenheim estimated that in FY 2021 (starting Oct 1, 2020), there will be at least 200,000 EB green cards available. That is, at least 60,000 out of the 226,000 FB visas available in FY 2020 will not be issued before the end of FY 2020, therefore, they will be added to the FY 2021 EB quota. This is good news for backlogged EB applicants, although some users on Trackitt have been asserting that the spillover would be sufficient to move the EB2 India date ahead several years, and that doesn’t seem to be correct. (But I’ll address this issue later in this post.)

I previously wrote that I wasn’t sure whether any spillover was going to happen at all—aren’t there enough applicants already inside the US to consume the FB numbers that cannot be used by applicants abroad? There had been speculation that the State Department was cooking the books in order to avoid issuing visas that they are legally required to issue. However, in the IIUSA webinar, Charlie explained that even the EB numbers will likely not be used up this year because of limited USCIS processing capacity. This suggests to me that the State Department has not been cooking the books in order to favour EB applicants over FB applicants. It is just that there is not enough processing capacity to use up the visas in either category. (Some people still, after all this time, think that Trump likes skilled immigrants. At this point, I don’t think there’s anything I can say to convince them that they’re wrong.)

One might wonder whether the unused EB visas this fiscal year will spill over to FB. The answer is sort of, but no. I claimed in my previous post that any unused EB visas will spill over to FB, and if they are still not used in FB the next year then they will spill over to EB again, and so on until the visas are used. It was pointed out to me that this could not possibly be true, because if it were true then it would have been possible to issue many more EB visas than have been issued to date. I looked into the issue a bit more, and it turns out that Congress wrote the EB to FB spillover rule in a way that makes it nearly impossible for FB to actually get any extra visas. The reason for this is that the FB quota is calculated using the formula MAX(226000, 480000 – IR + SO). Here, SO stands for the number of unused EB visas from the previous fiscal year, and IR stands for the number of immediate relative visas used during the previous fiscal year. In recent years, IR has generally been approximately 500,000. Because of this, it’s unlikely for us to ever see a situation where 480,000 – IR + SO is greater than 226,000. So, if Trump finds some way to get away with wasting a large number of EB visas (up to ~200,000 or so), he can make those visas permanently disappear.

Will Trump waste lots of EB visas in FY 2021? Maybe, maybe not. If USCIS tries to do so without reasonable justification, then I believe they will be subject to a lawsuit (which they will lose). But if they are able to claim that they don’t have enough processing capacity to process the additional EB adjustments that people would like to file in FY 2021, then I guess they will be able to get away with not issuing the green cards. Whether they will have enough capacity depends on what they will do with FB applicants in FY 2021 (I will discuss this issue in the next paragraph).

As we know, in the June and July visa bulletins, the FB cutoff dates did not move at a greater-than-usual pace despite the large number of FB applicants inside the US. I now believe that I understand why—it is because by the time the immigrant visa ban was announced (end of April), there was no longer enough time left to give those visas to people inside the US before the end of the fiscal year. An I-485 usually takes more than 5 months to adjudicate, and due to the pandemic, USCIS has had less processing capacity than usual; therefore, even in May, if the FB cutoff dates had been significantly advanced, allowing many applicants in the US to file, then the vast majority of those additional I-485s filed in May would not be able to be approved before the end of the fiscal year. At that point, the unused FB numbers would spill over to EB, so those I-485s would no longer be able to be approved using the FY 2020 quota. However, in such cases, the I-485s remain pending, which would mean that the applicants would be able to receive EADs, and be eligible for continuances in immigration court, while waiting for an immigrant visa number to become available. Given Trump’s agenda about immigration, it is understandable that he did not want to allow this [1]. I am not sure whether it is actually legal for USCIS to refuse to accept I-485s in this manner. The statutory criterion for filing for adjustment is that an immigrant visa must be immediately available at the time of filing; if there are so many available visas for applicants inside the US, because they are not available for applicants outside the US, then what authority do DHS/DOS have to disallow those people from filing? Well, I guess the answer is that the opportunity to use the adjustment of status procedure is a discretionary benefit: it is an alternative to consular processing that DHS allows at its discretion. So, I guess maybe they can say that if they believe that allowing an applicant to file an I-485 would create a high risk of that I-485 to be pending for a long time due to retrogression, then they have discretion to not accept that filing in the first place despite the fact that visas appear available. I am not sure.

The immigrant visa ban was extended last week, so that it will now continue through December. This again puts the FB applicants who are inside the US in a bad situation—for the same reason why DOS/DHS didn’t advance the FB cutoff dates rapidly in the June and July bulletins, I guess they still won’t do so in August, because again, allowing a flood of filings in August would result in most of those filings still being pending at the end of December. If the immigrant visa ban were not extended beyond December, the result would be that the visas would become available to applicants outside the US again, which would mean that the extra filings from people inside the US would again be subject to retrogression (possibly for many years). So I think that’s why it’s not going to happen. I suppose that if Trump gets re-elected and he continues extending the EO in 6-month increments, then DOS/DHS may have cover to indefinitely continue refusing to advance the dates more rapidly (based on the theoretical prospect of the ban ending in 6 months), drastically reducing the total number of FB visas that are issued in the next few years. This is another devious strategy that I imagine Miller may have devised. I think Congress should try to prevent this by changing the spillover rules. One attempt to do so is found in the HEROES Act, which is pending before the Senate, but I have no idea whether it’s likely to pass.

One other issue that I want to discuss is the allocation of the spilled-over visas in the EB categories. I discussed this issue a bit in my previous post, but I took some time to look into the issue more closely. There are some rules in INA 202 (8 USC §1152) that govern how the extra visas should be allocated to backlogged countries. First, (a)(3) says that if, after limiting each country to 7% of the total number of FB and EB visas, there is not enough demand to use up all the preference visas, then the remaining visas can be issued beyond the 7% limitation. In other words, DOS can advance the cutoff dates for that country. If there are multiple backlogged countries with demand for visas that were unused by the rest of the world, then DOS should attempt to allocate the extra visas to those countries according to the following rule: if natives of that country receive X% of the FB visas and Y% of the EB visas, then they should try to make X and Y as close as possible. In a typical year that means 1.61 FB visas should be issued for every one EB visa, to natives of any particular country. If a backlogged country is above that ratio, then it should get extra EB visas while the extra FB visas should be allocated to other backlogged countries; if it is below the ratio, then it should get extra FB visas while the extra EB visas should be allocated to other backlogged countries. Since preference immigrants from Mexico and the Philippines are overwhelmingly family-based while preference immigrants from India and China are overwhelmingly employment-based, it follows that, contrary to popular belief, Mexico and the Philippines should actually receive priority over India and China for EB visas that are not used by the rest of the world.

Then there is paragraph (a)(5)(A): If, after limiting each country to 7% of the total number of FB and EB visas, there is not enough demand to use up all the visas in any of the five EB preference categories, then the remaining visas in that preference category can be issued beyond the 7% limitation. This basically reiterates that there should not be wasted visas in any single preference category as long as there is sufficient demand for those visas. Thus, even though Mexico and the Philippines should receive priority over India and China for unused EB visas, because of the fact that Mexico and the Philippines have no EB-1 or EB-2 backlog anyway, it follows that all the extra EB-1 and EB-2 visas will be issued to Indians and Chinese.

The most confusing paragraphs are (e)(3) and (a)(5)(B). (e)(3) is another balancing rule similar to (e)(1), but here we are balancing across EB preference levels rather than between FB and EB. That is, if (a)(5)(A) allows extra EB visas to be issued to natives of a particular country, then DOS should attempt to make R_1 … R_5 as close to each other as possible, where R_i is the fraction of the EB-i visas that are issued to natives of that particular country. However, it’s not clear to me exactly what single metric is supposed to be optimized here by the allocation. (a)(5)(B) is some sort of limitation on (e)(3) that I am totally unable to understand.

So, after looking at these paragraphs, I’ve concluded that I have absolutely no idea how to answer the following questions: when Rest of World does not use up all the EB1 and EB2 visas, how many EB1 visas go to China and how many go to India, and how many EB2 visas go to China and how many go to India? People seem to assume that whatever EB2 visas are not used by Rest of World should just all go to Indians since they have the earliest priority dates, and that whatever EB1 visas are not used by Rest of World should similarly go to Indians until the Indian cutoff date catches up with the Chinese cutoff date at which point the two should be advanced in lockstep. However, I don’t think this is what INA 202 requires, but I have no idea what INA 202 does require.

All I know is that in FY 2021, backlogged EB applicants will receive a massive spillover; 2/7 of the the spilled-over visas will be distributed to EB1, 2/7 to EB2, and 2/7 to EB3; and Rest of World will almost certainly not use up all the EB1 and EB2 visas, just as they have not done so for the past few years, and that means extra visas for India and China, according to some distribution that I cannot predict. Maybe if I have time, I’ll try to file a Freedom of Information request with the State Department to get a hold of any internal documents they have that explain how this works. But if it’s all inside Charlie’s head, then there won’t be any documents to release.

[1] Well, I guess it was probably Miller who made the decision. Actually, I have to wonder whether Miller was responsible for the timing of the ban. If it had been announced later, there would not be as many visas left to waste in the year. If it had been announced earlier, there would be more time to process adjustments, so there would be less of an excuse to waste visas. Miller probably knows more about US immigration law than I do, so if I could see how the end of April was a particularly devious time to issue the ban, he probably could have seen that too. But I digress.

Legal speculation about recent visa bans

I previously published an FAQ about President Trump’s immigrant visa ban and work visa ban. You can read it here. The detailed answers to the questions therein are given on my US immigration FAQ on GitHub and backed by authoritative sources and reasoning. But some people also have questions whose answers are of a more speculative nature. This blog post addresses those questions.

Q1: What does section 5(b) of the work visa ban mean?

A1: Section 5(b) refers to the requirements of the Immigration and Nationality Act that employers petitioning for a green card in the EB3 or EB2 categories (excepting National Interest Waiver applicants) must obtain a labor certification (LC/PERM) and employers petitioning for H-1B status must file an labor condition application (LCA).

For an LC to be approved, the employer must demonstrate that there are not sufficient workers who are able, willing, qualified, and available (thus necessitating the importation of a permanent foreign worker) and that the employment of the foreign worker will not adversely affect the wages and working conditions of similarly employed workers in the US. For an LCA to be approved, the employer must demonstrate that it is offering at least the prevailing wage and that the H-1B worker will be employed under working conditions that will not adversely affect the working conditions of other workers similarly employed. The Department of Labor shall determine, in both cases, whether the employer has met the burden of proof.

Thus, the meaning of section 5(b) of the proclamation is that Trump is not sure whether the existing LC/LCA process is sufficiently stringent to guarantee that the EB2/EB3/H-1B programs do not disadvantage US workers in violation of the INA and that he would like the Department of Labor and DHS to consider whether new, more stringent regulations should be promulgated governing the LC and LCA/I-129 processes.

Q2: If Trump does publish new LC/LCA regulations, can they be used to retroactively revoke green cards and H-1B status?

A2: Although the text does extend to aliens who have been admitted … pursuant to an EB-2 or EB-3 immigrant visa, there is absolutely no chance that the courts will allow Trump to deport people who already have green cards just because he thinks that the previous regulations that allowed them to obtain a labor certification were not stringent enough, and I believe that Trump knows that, and he will not try to fight a battle that he cannot win.

In the case of H-1B workers, I think there is some legal argument that Trump could force some of them to leave if he believes that the LCA/I-129 process was not stringent enough, by ordering the Secretary of State to issue new regulations to revoke their visas under INA 221(i) and INA 237(a)(1)(B). I don’t expect him to actually do this, however, because it would be much easier to just deny extensions based on the new LCA/I-129 regulations. This would have a measurable effect of gradually reducing the number of H-1B workers in the US without going through protracted litigation related to the use of INA 221(i) and INA 237(a)(1)(B).

Q3: If Trump does publish new LC regulations, can he require I-485 applicants to undergo the new process prior to approval?

A3: If the regulation required aliens who had already submitted form I-485 (prior to the new regulations going into effect) to undergo recertification prior to I-485 approval, I think there’s about a 75% chance that such a provision would be illegal. Under AC21 106(c) (INA 204(j)/8 USC 1154(j)), an alien who has already filed an I-485 may, after 180 days have elapsed, switch to another job in the same occupation or a similar occupation without having to obtain a new labor certification. I think there’s a strong argument that if Congress has mandated that the alien can even take up a different job without a new labor market test, then the employer certainly cannot be required to perform a second labor market test for the same alien when it has already done so in the past. I don’t think such a requirement would be legal even if it contained an 180-day exemption. The reason for the 180-day waiting period is to merely ensure that the alien acted in good faith at the time of filing, and did not use that particular employer just so they could jump to another employer without redoing the green card process. If an alien whose I-485 had been pending for any length of time, whether greater or less than 180 days, were forced to undergo labor certification a second time prior to approval, I think that would violate the Congressional intent behind AC21.

Q4: If Trump does publish new LC regulations, can he use them to revoke I-140s that have already been approved, or require a new I-140 to be approved before proceeding to adjustment of status or immigrant visa processing?

A4: These questions seem to be closely related. I would guess that the courts would either allow both, or allow neither. I am not familiar enough with the Administrative Procedure Act, the applicable jurisprudence regarding retroactive application of regulations, and so on to even venture a vague guess as to whether the courts could strike down such regulations on those grounds. I did, however, find one news article in which an immigration lawyer argues that such regulations would violate INA 212(a)(5)(A) and AC21.

Q5: How is Trump’s proposal to allocate H-1B visas based on salary going to work?

A5: It has been reported that Trump wants to scrap the H-1B lottery and replace it with a system where the visas are allocated based on highest salary. No details of the plan have been released yet. The administration has not even said whether the system would attempt to normalize salary according to the geographical location and the occupation. (If such normalization is not done, then almost all of the visas would go to tech companies in Silicon Valley, Seattle, and NYC; other regions and industries, which also need H-1B workers, would not be able to compete.) In any case, regardless of how the system works, it is not clear whether it would be legal. The INA does not allow the limited pool of H-1B visas to be distributed based on salary; it simply specifies that once the quota runs out for a given fiscal year, no more aliens can be issued H-1B visas or H-1B status during that fiscal year. Thus, in the past, employers who did not file an H-1B petition early enough would not be able to import their desired candidate until the new quota became available for the following fiscal year, since all the visas would have been consumed already. Eventually, it got to the point where the number of petitions that were filed within the first week of the filing window was already enough to use up the entire quota for the year, so a random lottery system was introduced. One can justify the lottery as follows: It would be sort of silly if one petition that was delivered in the mail to USCIS on April 1st, 1 hour before another petition, received precedence on that basis. So instead, USCIS will take all petitions received in the first week of the filing window, and process them according to the legal fiction that some of them are randomly determined to have arrived earlier than others. If the Trump administration instead decided that the petitions with higher salary should be considered to have arrived earlier than others, he would be essentially introducing an adjudicative criterion that has no basis in the INA, so the courts probably would not allow this change, but I am not totally sure.

Q6: How likely is it that litigation against the immigrant visa ban and the work visa ban will succeed?

A6: In the immigrant visa ban case, the argument is essentially that Congress intended for a certain number of immigrant visas to be available per year in each category for family reunification, employment, and diversity, and that Trump should not be allowed to unilaterally reduce those numbers to zero using INA 212(f). My personal opinion is that the Supreme Court will let him get away with it based on the same reasoning as in the Trump v. Hawaii case, but that is just my personal speculation, and many actual lawyers disagree. In the work visa ban case, there are similar arguments, but there is also an additional argument that the ban violates the General Agreement on Trade in Services (GATS). The relationship between GATS and H-1B and L-1 visas is discussed here. However, it is not clear whether GATS is binding as a matter of domestic law. This issue is way beyond my depth, so I can’t really estimate the probability of this legal argument working, other than to say that it’s greater than zero.

Q7: What happened to Trump’s proposal to raise the fees for H-1B petitions to $20,000?

A7: The existence of such a proposal is merely speculative. Trump has not indicated that he plans on taking such an action. If he did attempt to do so, it could be argued that it would violate GATS (see previous Q/A). It could also be argued to be subverting Congressional intent of allowing the visas to be issued. (For example, if Trump made the fee $10 million, then it would obviously be an attempt to indirectly ban the approval of H-1B petitions, so the courts would not allow that. Whether they would allow a $20,000 fee is not totally clear, but I’m leaning toward no. On the other hand, a small fee increase would be completely legal, since Trump could argue that its purpose is to allow USCIS to recover the costs associated with whatever extreme vetting he wants them to do.)

Q8: What happened to Trump’s proposal to ban H-1B extensions for jobs that pay level 1 wages?

A8: Again, the existence of such a proposal, to not grant H-1B extensions for workers being paid level 1 wages unless their employer offered at least level 2 wages in the extension petition, is merely speculative. I think there’s about a 90% chance that such a regulation would be illegal, if it were to be published. Congress has set the criteria for aliens to obtain H-1B status, and the executive branch is responsible for devising a process, and promulgating regulations, to determine whether aliens seeking H-1B status meet those criteria. The executive has wide latitude in doing so, but may not invent new regulatory criteria out of thin air that are unrelated to the statutory criteria set by Congress. If Trump finds that allowing H-1B workers to remain at level 1 wages in a particular area, for a particular occupation, adversely affects US workers in that occupation in that area, then perhaps it would be within his authority to order the Department of Labor to not approve such extensions for that particular occupation, in that particular geographical area, pursuant to INA 212(n)(1)(A). But I think the statute requires such a determination to be made individually with respect to each occupation and each geographical area; Trump cannot thus issue a blanket finding with respect to level 1 wages across all areas and occupations.

Q9: Is Trump still planning to rescind the H-4 EAD rule?

A9: No word on that, but probably.

Q10: What about the proposed changes to the OPT program?

A10: There has been speculation that Trump is planning to eliminate or shorten the STEM OPT extension, or to limit it to particular sectors, or to limit it to students who graduate at the top of their class. Since the STEM OPT extension was created purely by regulation, and not statute, these changes would be fully within Trump’s authority to enact. However, until he actually publishes the regulations, we won’t know whether he is going to do it at all, and if so, what the provisions are.

Q11: Could Trump stop issuing EADs to individuals with pending Adjustment of Status applications, thus eliminating the employment authorization of tens of thousands of aliens who are in the backlog waiting for a green card?

A11: Yes, that’s a regulatory change that would be within his authority to enact, since the AOS EAD was created by regulation in 1981 and not by statute. The notice in the Federal Register explained that these individuals will receive unrestricted employment authorization soon anyway (since they will have a green card), so that it made sense for INS to grant some such individuals (who might not otherwise have a means of obtaining employment authorization for supporting themselves in the US) an EAD at its own discretion. But Trump could very well argue that such discretion should generally not be exercised favourably due to the current unemployment crisis, and use that as a justification for eliminating the AOS EAD at least temporarily (though, as the Supreme Court’s recent DACA decision indicated, he would at least need to consider reliance interests as part of the rulemaking process). Despite the fact that Trump could very well do this, I currently don’t expect him to. Even the speculations based on supposed leaks of would be in the work visa ban did not suggest that Trump was considering such an action.

Comments about today’s DACA ruling

Today, the Supreme Court issued a 5–4 ruling that the Trump administration’s rescission of the DACA program was unlawful. The opinion of the Court was delivered by Roberts, with Ginsburg, Breyer, and Kagan joining in full, and Sotomayor concurring as to the result. You can read the ruling here.

Last year, I correctly predicted how the justices would vote. Now it’s time to give some further comments about the ruling.

First, the Court did not rule on whether DACA is actually legal. In fact, the Court held that Attorney General’s finding that DACA is illegal provides a justification for rescinding the associated benefits such as work authorization (but not the grant of deferred action itself). However, DHS still must consider reliance interests before promulgating the rescission of benefits. DHS also did not provide adequate justification for the rescission of the entire program, as there had not been a finding of illegality of the deferred action itself.

Second, the Court did not rule that DACA rescission needs to go through the notice-and-comment rulemaking procedure. In fact, it noted that such claims were already raised in the lower courts and rejected there. For example, the 9th circuit concluded in DHS v. Regents of UC that both the creation of DACA, and its rescission, are general statements of policy and are thus exempt from notice-and-comment. This fact is very important, because notice-and-comment requires at least a 30 day period for the public to submit comments, and the agency is required to review every single comment and address the substantive subject matter of those comments in its rulemaking. In practice, this is usually done by categorizing the comments according to their key points and responding to each point identified, as obviously, it would not be practical to provide a response to each comment separately. Still, given that a hypothetical notice of proposed rulemaking regarding DACA would likely attract hundreds of thousands of public comments, it would take DHS several months to review and categorize all the comments. Because the Court ruled that this procedure is not required, DHS could potentially move much faster.

Third, the Court also did not specify the detailed requirements that a rescission would need to satisfy in order to be lawful. It notes that DHS should consider reliance interests in determining how the wind-down should be performed—for example, in considering the reliance interests, DHS could have decided on a longer transition period or provided for case-by-case discretion. But after balancing all relevant considerations, DHS is not required to arrive at any particular conclusion.

Fourth, as the Court did not rule today on whether DACA is legal or not, I believe that if an entity had standing to challenge DACA itself, arguing that it’s unconstitutional for the executive branch to grant deferred action in such a form and that the plaintiff were injured by this action, then there’s still some possibility that the Court could make such a ruling in the future. The kind of entity with the strongest claim to standing would be a State, as in the United States v. Texas case regarding DAPA and the DACA expansion. I don’t think it’s likely that a State will actually mount such a challenge against DACA, because even a majority of Republicans support DACA now. But there could potentially be other entities with standing, such as workers alleging that DACA unlawfully increases competition for jobs (cf. the Save Jobs USA lawsuit regarding the H-4 EAD program).

Where does this leave us? Basically, it means DHS could issue a new memo rescinding DACA, but they must provide sufficient justifications for both the rescission of the deferred action itself and the associated benefits. DHS could potentially act quickly to issue a new memo, in which it makes a finding, based on law, that it lacks the authority to grant deferred action, and, after considering reliance interests and other relevant considerations, determines that DHS will end DACA. But what form would that take?

DHS could move to immediately end the DACA program and revoke all existing EADs granted under it, rendering all current DACA beneficiaries potentially subject to immediate deportation and making it illegal for their current employers to keep them on the payroll.

Or, DHS could announce that they will stop accepting new applications and renewals after some transition period (maybe 6 months, maybe more, maybe less). In that case, some grants of deferred action would begin to expire within 6 months (as one can renew up to 6 months in advance of expiration), which gets us almost to the end of Trump’s term. In that case, if Biden wins the election in November, the damage done to DACA will have been minimal.

Between the two options, I think the latter is much more likely. This is for two reasons. First, the former option would make the administration more vulnerable to further legal challenges based on allegations that the rationale provided was not sufficient to justify such extreme action (notwithstanding the fact that the administration might ultimately prevail in that case). Second, by taking the latter option, Trump can emphasize that he’s doing as much as he can to fulfill his promise of enforcing the immigration laws, but his efforts will prove futile unless he is elected to a second term. This would be a smart political strategy for him.

In conclusion, if you support DACA, then be sure to do your part in getting Biden elected in November and flipping the Senate. (While non-citizens cannot vote and cannot legally spend money on or donate for the purpose of electioneering communications, we can still do our part in raising awareness and advocating for what we believe in.) If Trump is re-elected, then not only does he have more than enough time to end DACA legally, but he could also potentially replace Justice Ginsburg, without whom today’s ruling would not have been possible. If Trump loses but the GOP manages to keep 51 seats in the Senate, then Mitch McConnell will block any efforts at immigration reform and the future of DACA recipients will remain uncertain. There would also be a small risk that SCOTUS would revisit DACA and end it for good, over the objections of the Biden administration. In that case, the administration could still do a lot to delay deportations, but would be enjoined from issuing work permits, which would severely limit the options for DACA people to support themselves.

How does immigrant visa spillover work?

Update (June 27, 2020): Some of the information in this post is inaccurate. See this newer post for corrections and clarifications.

There has been some recent speculation that 52,000 visas could spill over from the family-based quota to the employment-based quota due to Trump’s recent executive order to ban immigrants from entering the US for 60 days (which many people believe will be extended, perhaps until the election or even longer). There have been many arguments about the mechanics of spillover on Trackitt, an immigration forum largely populated by Indian people, who face very long backlogs for employment-based immigrant visas. However, the law is quite clear, so much of the controversy seems unnecessary.

Where did the 52,000 figure come from?

The figure of 52,000 comes from a tweet by the Migration Policy Institute that 26,000 green cards would be blocked by the EO during each month it remains in effect, which means 52,000 over a period of 60 days. The MPI doesn’t explain their methodology, but I think we can draw some inferences.

The MPI seems to have gotten the 26,000 figure by taking the total of 315,403 and dividing by 12. This total includes family-based, employment-based, and diversity visas. So we can immediately conclude that MPI did not estimate 52,000 family-based immigrants would be blocked. That was, rather, their total estimate across all three categories. Rather, their estimate is that 5,565 immediate relative immigrants and 15,409 family-based preference immigrants would be blocked per month.

Second, the MPI’s figures look very similar to the official State Department figures for immigrant visas issued abroad in 2019. For example, the MPI’s estimate of 3,432 for EB-2 is very close to the State Department figure of 3,497 EB-2 immigrant visas issued in 2019, which is substantially less than the actual annual EB-2 quota of roughly 40,000. From this we can infer that the MPI numbers mean something like we estimate that 52,000 people who would have received immigrant visas over the next 60 days, now will not as a result of the EO.

This does not mean that 52,000 visas will go unused! Since the EO does not block green cards for applicants who are already in the US, there is a possibility that some or all of those 52,000 visas can be issued to applicants in the US, instead of the people outside the US who would have received them if not for the EO. (Note: An applicant in the US who receives a green card consumes an immigrant visa, but is not actually physically issued a visa.) The MPI figures simply do not answer the question of whether any immigrant visas will be unused this year.

Will any family-based visas actually go unused this year?

The May 2020 visa bulletin was released on April 24, several days later than expected, since it could not be cleared for release until Trump’s executive order had been finalized. However, astute readers noticed that the date April 6, 2020 was printed at the bottom of the bulletin, suggesting that the cutoff dates had already been calculated by then. Indeed, the movement in cutoff dates was, perhaps, no more than would have been expected without the EO. For example, the F3 and F4 Mexico cutoff dates, which advanced 1 month in the April bulletin, again advanced 1 month in the May bulletin.

Now, in order to use up all the family-based visas for this fiscal year, the State Department must move the cutoff dates far enough ahead so that enough people are able to apply for their visas. Since most family-based applicants live outside the US, and many of them can no longer receive a visa due to the EO, it is necessary to move the cutoff dates more quickly so the visas can instead be used by applicants inside the US. The fact that this does not seem to have happened has made some immigration lawyers concerned. However, until the June 2020 visa bulletin is released, it’s too early to panic—again, the May 2020 cutoff dates may simply not have taken into account the EO yet. (Update (June 27, 2020): It looks like they decided not to move the dates rapidly. See the newer post linked at the top of this post for a possible explanation of why.)

Most family-based immigrants on the waiting list are outside the US. This is because most of them cannot easily obtain a long-term visa, such as a student visa or work visa, that would enable them to live in the US while they wait for an immigrant visa to become available. This fact has led some to speculate whether there are just not enough of them inside the US to use up the rest of the family-based immigration quota for the current fiscal year. For example, if, hypothetically speaking (I am just pulling numbers out of thin air here), 120,000 of the 226,000 family-based immigrant visas this year had already been issued, and there were 85,000 remaining applicants waiting inside the US, then at least 21,000 visas would go unused. However, I don’t think that this is the case. (Update (June 27, 2020): Since they decided not to move the dates rapidly, this paragraph is moot. Most of the applicants inside the US will not receive a green card this year even though green cards should be available to them. See the newer post linked at the top of this post.)

Greg Siskind, an immigration lawyer, has made the following comment that most casual readers won’t understand: They could have moved all the Mexican categories to May 2001 (they’re backed up to the 90s except F2A) so that the 245i folks in the US could file adjustments to fill in the gap from IV processing abroad. Siskind is referring to INA 245(i), which, in short, allows certain people with priority dates earlier than May 2001 to obtain a green card even if they are currently residing in the US without authorization. In other words, if the State Department is having a hard time issuing all the remaining family-based visas this year, they should advance the Mexico cutoff dates, possibly all the way up to May 2001, to give more people a chance to apply, as there is probably a substantial population of Mexicans inside the US who may be eligible for green cards under INA 245(i). The number of such individuals is impossible to determine accurately, so the State Department cannot in good faith say well, we tried to issue all the visas available, but we couldn’t do so because of the EO unless they’ve given all the 245(i) folks an opportunity to apply. (Update (June 27, 2020): Looks like this paragraph is wrong—they are not allowing these people to apply, most likely because any application filed in May or later could not be approved by the end of September anyway. See the newer post linked at the top of this post.)

Some immigration lawyers think that the administration is going to try to waste family-based visas on purpose as part of their agenda to curtail immigration. If the June 2020 visa bulletin rolls around and it really does seem that they are not making an effort to advance the dates, then it is likely that immigrant advocate groups will have some members of Congress ask the State Department why they are not on track to issue all the visas to eligible applicants—and there may be legal challenges if the answer is not satisfactory. So I believe that while some family-based visas may go unused this year, the chances of the number being significantly affected by the EO are slim (i.e., there is a slim chance that any judicial relief gets held up until after the end of the fiscal year). (We should note that there was already some spillover into the employment-based quota this year, indicating that not all of last year’s family-based visas were used. Nobody seems to know exactly why, so the same might happen this year, EO or no EO.) (Update (June 27, 2020): Looks like I was wrong; a massive number of FB green cards will go unused this year. See the newer post linked at the top of this post.)

If some visas are unused, would they actually spill over?

According to INA 201(d)(1)(B), if the full quota of family-based visas is not used up in this fiscal year, then the unused numbers are added to next year’s employment-based immigration quota. While Trump can suspend issuance of visas pursuant to INA 212(f), he is without power to block the spillover provisions. Even if Trump takes further actions to block issuance of employment-based green cards next year, in an effort to prevent immigrants from benefitting from the spillover, he cannot actually waste any green cards. If the spilled-over numbers, added to the employment-based quota next year, are not used, they will just spill over as family-based quota the following year, and so on indefinitely back and forth between the two categories until either Trump is out of office, or Congress changes the law. (Update (June 27, 2020): This is wrong. If the visas spill over from FB to EB, but then they are not used in EB, then they will actually be lost. See the newer post linked at the top of this post.)

Unused diversity visa numbers, however, do not spill over. They are neither added to next year’s diversity visa quota, or to any other category.

If visas spill over to employment-based immigrants, how will they be allocated?

INA 201(d)(1)(B) prescribes the worldwide level of employment-based immigrants. INA 203(b) prescribes that the worldwide level shall be allocated as follows: 2/7 to EB-1, 2/7 to EB-2, 2/7 to EB-3, 1/14 to EB-4, and 1/14 to EB-5. Some people have speculated that the spillover visas will all go to the most backlogged people, namely Indian-born EB-2 applicants; this is false. Some have speculated that the spillover visas will all go to EB-1; this is also false. The EB-2 and EB-3 quotas will increase proportionally. This is very clear from the statute; there is no ambiguity. Some have speculated that none of the spillover numbers can be allocated to Indians because the number of available visas for natives of any single country is fixed. This is also false, since the 7% limitation applies to the total worldwide level of preference-based immigrants according to INA 202(a)(2), which, as previously mentioned, is not a fixed number but, according to INA 201, depends on how many visas spilled over from the previous year.

Thus, if any numbers spill over, then the State Department will allocate them the same way they would have allocated the usual quota—just with all the numbers scaled up proportionally. Because EB-1 Rest of World is unlikely to use up all the numbers (whether there is spillover or no spillover), that means that the spilled-over visas allocated to EB-1 (namely 2/7 of the total) will mostly go to the most backlogged (i.e., Indian-born applicants) due to INA 202(a)(5). Another 2/7 would spill over to EB-2, which would also be allocated in the usual way, but if Rest of World does not use up all the EB-2 numbers, then any additional numbers would again be allocated to India. In EB-3, demand from Rest of World exceeds supply, so if current patterns continue, then EB-3 China and EB-3 India would likely only receive 7% of any spilled-over numbers. (Update (June 27, 2020): I’m not sure whether the most backlogged rule is correct. So I don’t know how the extra EB-1 and EB-2 visas will be divided between China and India. See the newer post linked at the top of this post.)

Conclusion

It’s not likely that there will be any unused family-based visas to spill over. But if there are any unused family-based visas, they will spill over to employment-based immigrants and Trump cannot prevent that. If such spillover does occur, then it will be distributed evenly to EB-1, EB-2, and EB-3, and within each preference level, Rest of World will still be entitled to 86% of the spilled-over visas, which will only go to India if there are not enough Rest of World applicants. Thus, spillover could significantly benefit EB-1 India and EB- 3 Rest of World, whereas EB-3 India and all three Chinese categories would likely receive little benefit (though EB-5 is another story). The EB-2 Rest of World and EB-2 India situations are harder to predict (although EB-2 India is so backlogged that even if it does end up receiving additional unused numbers from EB-2 Rest of World, the movement will still not be that much). (Update (June 27, 2020): I’m not sure whether this is correct anymore; EB1 and EB2 China may receive more visas than I expected, but the truth is that I just don’t know. See the newer post linked at the top of this post.)

Armchair lawyering about the recent EO

The Attorney General of New York is making preparations to challenge Trump’s executive order banning most immigrants from entering the US “temporarily” under INA 212(f) (8 USC §1182(f)). I am sure there are various other groups also interested in filing legal challenges.

The order can be found here.

Can the President ban all immigration?

Some commentators suggest that INA 212(f) doesn’t give the President authority to end all immigration. Here, all has been placed in quotation marks since the EO does not ban all immigration anyway; certain categories such as spouses of US citizens are exempted. The idea is that bans based on 212(f) that are too broad may not be allowable.

Yet, the text clearly says the President may suspend the entry of all aliens or any class of aliens.

Some argue that, while the Trump v. Hawaii case established that the President may ban all aliens from particular countries, that it would be contrary to the INA for the President to indefinitely end the issuance of visas in entire preference categories – for example, as Trump is banning all F4 immigrants (brothers and sisters of US citizens) from entering the US (unless they qualify for an exemption based on being in the US already) this could be argued to contravene an imagined intent of Congress in enacting INA 201 and INA 203 of making at least 65,000 F4 immigrant visas available each fiscal year.

This argument is essentially about timing: it is clear from the statute that the President may ban all aliens, but the argument is that this power could not be used to establish a ban of such duration that it would result in the visas allocated by Congress going wasted. I don’t think this argument is convincing. The statute does say the President can suspend entry for such period as he shall deem necessary, which is pretty close to explicitly saying there’s no limit on the President’s discretion to set the duration of the suspension.

Is Trump’s use of INA 212(f) an unconstitutional delegation?

Congress is not constitutionally permitted to delegate its legislative power to the executive branch or any other entity, but may enact statutes that enable the executive branch to exercise discretion over policy, if it provides an intelligible principle. For example, in INA 212(a)(9)(B), Congress banned aliens from entering the United States if they were unlawfully present for more than 180 days, but granted the Attorney General discretion to waive this inadmissibility in certain cases if it would cause extreme hardship to a US citizen or LPR relative. In this case, the executive is permitted to set policy regarding which aliens can receive waivers, but Congress provided the guiding principle that the standard of eligibility for such waiver must be based on a level of extreme hardship.

A recent case in the United States District Court for the District of Oregon concerned whether Trump’s use of INA 212(f) to bar the entry of aliens who could not demonstrate that they would be able to obtain certain types of health insurance coverage (Case No. 3:19-cv-1743-SI). The plaintiffs in this case argued that this use of INA 212(f) involved an unconstitutional delegation. The court agreed and granted a preliminary injunction.

The court’s opinion stated that INA 212(f) is overbroad in delegation, providing no intelligible principle for the Presidents exercise of discretion, since the only condition is that the President must find that the entry of aliens would be detrimental to the interests of the United States. The court thus found that Congress cannot delegate power to the President in this manner. The defendants pointed out that Supreme Court precedent (Knauff v. Shaughnessy, 338 US 537 (1950)) established that the President’s inherent constitutional power over foreign affairs includes the power to restrict the entry of aliens (so that INA 212(f) confers little or no additional power upon the President but merely reaffirms power that the President already possesses). The district court’s opinion, however, was that such inherent power of the President over immigration does not extend to restricting immigration for domestic policy purposes (in contrast to e.g. national security or foreign relations concerns).

In my opinion, this type of argument, if it is raised in the cases concerning the present executive order, would not be likely to persuade the Supreme Court. I believe the Supreme Court would almost certainly find that the President’s inherent authority to restrict the entry of aliens is not limited only to situations implicate national security or foreign relations concerns.

Conclusion

Based on what we know about the current Supreme Court, I think it’s overwhelmingly unlikely that they would strike down the recent EO. In fact, I think it’s very likely that they would quickly reverse any stay of the EO issued by a lower court. I think it’s almost irresponsible for the mainstream media to give false hope to immigrants that a court challenge would be likely to succeed. Then again, there are actual legal experts who disagree with me, so take this with a grain of salt.