Arrow Research search

Author name cluster

Alexander A. Razborov

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

21 papers
2 author rows

Possible papers

21

SAT Conference 2020 Conference Paper

On CDCL-Based Proof Systems with the Ordered Decision Strategy

  • Nathan Mull
  • Shuo Pang 0002
  • Alexander A. Razborov

Abstract We prove that CDCL SAT-solvers with the ordered decision strategy and the DECISION learning scheme are equivalent to ordered resolution. We also prove that, by replacing this learning scheme with its opposite, which learns the first possible non-conflict clause, they become equivalent to general resolution. In both results, we allow nondeterminism in the solver’s ability to perform unit propagation, conflict analysis, and restarts in a way that is similar to previous works in the literature. To aid the presentation of our results, and possibly future research, we define a model and language for CDCL-based proof systems – particularly those with nonstandard features – that allow for succinct and precise theorem statements.

Details

STOC Conference 2018 Conference Paper

Clique is hard on average for regular resolution

  • Albert Atserias
  • Ilario Bonacina
  • Susanna F. de Rezende
  • Massimo Lauria
  • Jakob Nordström
  • Alexander A. Razborov

We prove that for k ≪ n 1/4 regular resolution requires length n Ω( k ) to establish that an Erdos-Renyi graph with appropriately chosen edge density does not contain a k-clique. This lower bound is optimal up to the multiplicative constant in the exponent, and also implies unconditional n Ω( k ) lower bounds on running time for several state-of-the-art algorithms for finding maximum cliques in graphs.

Details

FOCS Conference 2014 Conference Paper

On the AC0 Complexity of Subgraph Isomorphism

  • Yuan Li
  • Alexander A. Razborov
  • Benjamin Rossman

Let P be a fixed graph (hereafter called a “pattern”), and let SUBGRAPH(P) denote the problem of deciding whether a given graph G contains a subgraph isomorphic to P. We are interested in AC0-complexity of this problem, determined by the smallest possible exponent C(P) for which SUBGRAPH(P) possesses bounded-depth circuits of size n C(P)+o(1). Motivated by the previous research in the area, we also consider its “colorful” version SUBGRAPHcol(P) in which the target graph G is V(P)colored, and the average-case version SUBGRAP Have (P) under the distribution G(n, n -θ (P)), where θ(P) is the threshold exponent of P. Defining C col (P) and Cave(P) analogously to C(P), our main contributions can be summarized as follows. (1) C col (P) coincides with the tree-width of the pattern P within a logarithmic factor. This shows that the previously known upper bound by Alon, Yuster, Zwick [3] is almost tight. (2) We give a characterization of Cave(P) in purely combinatorial terms within a multiplicative factor of 2. This shows that the lower bound technique of Rossman [21] is essentially tight, for any pattern P whatsoever. (3) We prove that if Q is a minor of P then SUBGRAPH col (Q) is reducible to SUBGRAPH col (P) via a linear-size monotone projection. At the same time, we show that there is no monotone projection whatsoever that reduces SUBGRAPH(M 3 ) to SUBGRAPH(P 3 + M 2 ) (P 3 is a path on 3 vertices, Mk is a matching with k edges, and “+” stands for the disjoint union). This result strongly suggests that the colorful version of the subgraph isomorphism problem is much better structured and well-behaved than the standard (worstcase, uncolored) one.

Details

CSL Conference 2009 Conference Paper

The Ackermann Award 2009

  • Johann A. Makowsky
  • Alexander A. Razborov

Abstract The fifth Ackermann Award is presented at this CSL’09, held in Coimbra, Portugal. This is the third year in which the EACSL Ackermann Award is generously sponsored. Our sponsor is the world’s leading provider of personal peripherals, Logitech S. A. , situated in Romanel, Switzerland. Eligible for the 2009 Ackermann Award were PhD dissertations in topics specified by the EACSL and LICS conferences, which were formally accepted as PhD theses at a university or equivalent institution between 1. 1. 2007 and 31. 12. 2008. The Jury received 12 nominations for the Ackermann Award 2009. The candidates came from 10 different nationalities from Europe, North America and Asia and received their PhDs in 9 different countries in Europe and North America.

Details

FOCS Conference 2008 Conference Paper

The Sign-Rank of AC^O

  • Alexander A. Razborov
  • Alexander A. Sherstov

The sign-rank of a matrix A = [A ij ] with plusmn1 entries is the least rank of a real matrix B = [B ij ] with A ij B ij > 0 for all i, j. We obtain the first exponential lower bound on the sign-rank of a function in AC 0. Namely, let f(x, y) = Lambda i=1 m Lambda j=1 m 2 (x ij Lambda y ij ). We show that the matrix [f(x, y)] x, y has sign-rank 2 Omega(m). This in particular implies that Sigma 2 cc nsubeUPP cc, which solves a long-standing open problem posed by Babai, Frankl, and Simon (1986). Our result additionally implies a lower bound in learning theory. Specifically, let Phi 1, .. ., Phi r: {0, 1} n rarrRopf be functions such that every DNF formula f: {0, 1} n rarr {-1, +1} of polynomial size has the representation f equiv sign(a 1 Phi 1 + hellip + a r Phi r ) for some reals a 1, .. ., a r. We prove that then r ges 2 Omega(n 1/3 ), which essentially matches an upper bound of 2 Otilde(n 1/3 ) due to Klivans and Servedio (2001). Finally, our work yields the first exponential lower bound on the size of threshold-of-majority circuits computing a function in AC 0. This substantially generalizes and strengthens the results of Krause and Pudlak (1997).

Details

FOCS Conference 2006 Conference Paper

An Omega(n 1/3 ) Lower Bound for Bilinear Group Based Private Information Retrieval

  • Alexander A. Razborov
  • Sergey Yekhanin

A two server private information retrieval (PIR) scheme allows a user U to retrieve the i-th bit of an n-bit string x replicated between two servers while each server individually learns no information about i. The main parameter of interest in a PIR scheme is its communication complexity, namely the number of bits exchanged by the user and the servers. A large amount of effort has been invested by researchers over the last decade in search for efficient PIR schemes. A number of different schemes ((B. Chor. O. Goldreich. E. Kushilevitz. and M. Sudan, 1998), (A. Beimel and Y. Ishai, 2001), (D. Woodruff and S. Yekhanin, 2005)) have been proposed, however all of them ended up with the same communication complexity of O(n 1/3 ). The best known lower bound to date is 5 log n by (S. Wehner and R. de Wolf, 2005). The tremendous gap between upper and lower bounds is the focus of our paper. We show an Omega(n 1/3 ) lower bound in a restricted model that nevertheless captures all known upper bound techniques. Our lower bound applies to bilinear group based PIR schemes. A bilinear PIR scheme is a one round PIR scheme, where user computes the dot product of servers' responses to obtain the desired value of the i-th bit. Every linear scheme can be turned into a bilinear one with an asymptotically negligible communication overhead. A group based PIR scheme is a PIR scheme that involves servers representing database by a function on a certain finite group G, and allows user to retrieve the value of this function at any group element using the natural secret sharing scheme based on G. Our proof relies on representation theory of finite groups

Details

CSL Conference 2005 Conference Paper

The Ackermann Award 2005

  • Erich Grädel
  • Johann A. Makowsky
  • Alexander A. Razborov

Abstract At the annual conference of the EACSL, CSL’04, it was suggested to the newly elected president of EACSL that steps be taken to make the Annual Conference of EACSL even more attractive for young researchers in Logic and Computer Science. In response to this suggestion, the EACSL Board decided in November 2004 to launch the Ackermann Award, the EACSL Outstanding Dissertation Award for Logic in Computer Science.

Details

TCS Journal 2003 Journal Article

Resolution lower bounds for the weak functional pigeonhole principle

  • Alexander A. Razborov

We show that every resolution proof of the functional version FPHP n m of the pigeonhole principle (in which one pigeon may not split between several holes) must have size exp(Ω(n/(log m)2)). This implies an exp(Ω(n1/3)) bound when the number of pigeons m is arbitrary.

Details DOI

FOCS Conference 2002 Conference Paper

Satisfiability, Branch-Width and Tseitin Tautologies

  • Michael Alekhnovich
  • Alexander A. Razborov

For a CNF /spl tau/, let w/sub b/(/spl tau/) be the branch-width of its underlying hypergraph. In this paper we design an algorithm for solving SAT in time n/sup O(1)/2/sup O(w(b)(/spl tau/))/. This in particular implies a polynomial algorithm for testing satisfiability on instances with tree-width O(log n). Our algorithm is a modification of the width based automated theorem prover (WBATP) which is a popular (at least on the theoretical level) heuristic for finding resolution refutations of unsatisfiable CNFs. We show that instead of the exhaustive enumeration of all provable clauses, one can do a better search based on the Robertson-Seymour algorithm for approximating the branch-width of a graph. We call the resulting procedure Branch-Width Based Automated Theorem Prover (BWBATP). As opposed to WBATP, it always produces regular refutations. Perhaps more importantly, the running time of our algorithm is bounded in terms of a clean combinatorial characteristic that can be efficiently approximated, and that the algorithm also produces, within the same time, a satisfying assignment if /spl tau/ happens to be satisfiable. In the second part of the paper we investigate the behavior of BWBATP on the Well-studied class of Tseitin tautologies. We argue that in this case BWBATP is better than WBATP. Namely, we show that its running time on any Tseitin tautology /spl tau/ is |/spl tau/|/sup O(1)/. 2/sup O(w(/spl tau//spl boxvr/O))/ as opposed to the obvious bound n/sup O(w(/spl tau//spl boxvr/O))/ provided by WBATP. This in particular implies that Resolution is automatizable on those Tseitin tautologies for which we know the relation w(/spl tau//spl boxvr//spl phi/) /spl les/ O(log S(/spl tau/)). We identify one such subclass and prove partial results toward establishing this relation for larger classes of graphs.

Details

FOCS Conference 2001 Conference Paper

Lower Bounds for Polynomial Calculus: Non-Binomial Case

  • Michael Alekhnovich
  • Alexander A. Razborov

We generalize recent linear lower bounds for Polynomial Calculus based on binomial ideals. We produce a general hardness criterion (that we call immunity) which is satisfied by a random function and prove linear lower bounds on the degree of PC refutations for a wide class of tautologies based on immune functions. As some applications of our techniques, we introduce mod/sub p/ Tseitin tautologies in the Boolean case (e. g. in the presence of axioms x/sub i//sup 2/=x/sub i/), prove that they are hard for PC over fields with characteristic different from p, and generalize them to Flow tautologies which are based on the MAJORITY function and are proved to be hard over any field. We also show the /spl Omega/(n) lower bound for random k-CNFs over fields of characteristic 2.

Details

FOCS Conference 2001 Conference Paper

Resolution is Not Automatizable Unless W[P] is Tractable

  • Michael Alekhnovich
  • Alexander A. Razborov

We show that neither Resolution nor tree-like Resolution is automatizable unless the class W[P] from the hierarchy of parameterized problems is fixed-parameter tractable by randomized algorithms with one-sided error.

Details

FOCS Conference 2000 Conference Paper

Pseudorandom Generators in Propositional Proof Complexity

  • Michael Alekhnovich
  • Eli Ben-Sasson
  • Alexander A. Razborov
  • Avi Wigderson

We call a pseudorandom generator G/sub n/: {0, 1}/sup n//spl rarr/{0, 1}/sup m/ hard for a propositional proof system P if P can not efficiently prove the (properly encoded) statement G/sub n/(x/sub 1/, .. ., x/sub n/)/spl ne/b for any string b/spl epsiv/{0, 1}/sup m/. We consider a variety of "combinatorial" pseudorandom generators inspired by the Nisan-Wigderson generator on one hand, and by the construction of Tseitin tautologies on the other. We prove that under certain circumstances these generators are hard for such proof systems as resolution, polynomial calculus and polynomial calculus with resolution (PCR).

Details

FOCS Conference 1998 Conference Paper

Exponential Complexity Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions Over Finite Fields

  • Dima Grigoriev
  • Alexander A. Razborov

A depth 3 arithmetic circuit can be viewed as a sum of products of linear functions. We prove an exponential complexity lower bound on depth 3 arithmetic circuits computing some natural symmetric functions over a finite field F. Also, we study the complexity of the functions f: D/sup n//spl rarr/F for subsets D/spl sub/F. In particular, we prove an exponential lower bound on the complexity of a depth 3 arithmetic circuit which computes the determinant or the permanent of a matrix considered as functions f: (F*)n/sup 2//spl rarr/F.

Details

MFCS Conference 1997 Conference Paper

On O versus NP \cap co-NP for Decision Trees and Read-Once Branching Programs

  • Stasys Jukna
  • Alexander A. Razborov
  • Petr Savický
  • Ingo Wegener

Abstract It is known that if a Boolean function f in n variables has a DNF and a CNF of size ≤ N then f also has a (deterministic) decision tree of size exp( O (log n log 2 N )). We show that this simulation cannot be made polynomial: we exhibit explicit Boolean functions f that require deterministic trees of size exp ( Ω (log 2 N )) where N is the total number of monomials in minimal DNFs for f and - f. Moreover, we exhibit new examples of explicit Boolean functions that require deterministic read-once branching programs of exponential size whereas both the functions and their negations have small nondeterministic read-once branching programs. One example results from the Bruen-Blokhuis bound on the size of nontrivial blocking sets in projective planes: it is remarkably simple and combinatorially clear. Whereas other examples have the additional property that f is in AC°.

Details
v2026.09.13