by

Open Problems from Lovasz and Plummer’s Matching Theory Book

I always have exactly one bed-time mathematical book to read (for an hour) before going to sleep. It helps me learn new concepts and hopefully stumble upon interesting open problems. Matching Theory by Laszlo Lovasz and Michael D. Plummer has been my bed-time book for the last six months. I bought this book 3 years back (during my PhD days) but never got a chance to read it. This book often disappears from Amazon’s stock. I guess they are printing it on-demand.

If you are interested in learning the algorithmic and combinatorial foundations of Matching Theory (with a historic perspective), then this book is a must read. Today’s post is about the open problems mentioned in Matching Theory book. If you know the status (or progress) of these problems, please leave a comment.

—————————————————————————-

1 . Consistent Labeling and Maximum Flow 

Conjecture (Fulkerson) : Any consistent labelling procedure results in a maximum flow in polynomial number of steps.

—————————————————————————-

2. Toughness and Hamiltonicity

The toughness of a graph G, t(G) is defined to be +\infty, if G = K_n and to be min(|S|/c(G-S)), if G \neq K_n. Here c(G-S) is the number of components of G-S.

Conjecture (Chvatal 1973) : There exists a positive real number t_0 such that for every graph G, t(G) \geq t_0 implies G is Hamiltonian.

—————————————————————————-

3. Perfect Matchings and Bipartite Graphs

Theorem : Let X be a set, X_1, \dots, X_t \subseteq X and suppose that |X_i| \leq r for i = 1, \dots, t. Let G be a bipartite graph such that

a) X \subseteq V(G),

b) G - X_i has a perfect matching , and

c) if any edge of G is deleted, property (b) fails to hold in the resulting graph.

Then, the number of vertices in G with degree \geq 3 is at most r^3 {t \choose 3}.

Conjecture : The conclusion of the above theorem holds for non-bipartite graphs as well.

—————————————————————————-

4. Number of Perfect Matchings

Conjecture (Schrijver and W.G.Valiant 1980) : Let \Phi(n,k) denote the minimum number of perfect matchings a k-regular bipartite graph on 2n points can have. Then, \lim_{n \to \infty} (\Phi(n,k))^{\frac{1}{n}} = \frac{(k-1)^{k-1}}{k^{k-2}}.

—————————————————————————-

5. Elementary Graphs

Conjecture : For k \geq 3 there exist constants c_1(k) > 1 and c_2(k) > 0 such that every k-regular elementary graph on 2n vertices, without forbidden edges , contains at least c_2(k){\cdot}c_1(k)^n perfect matchings. Furthermore c_1(k) \to \infty as k \to \infty.

—————————————————————————-

6. Number of colorations

Conjecture (Schrijver’83) : Let G be a k-regular bipartite graph on 2n vertices. Then the number of colorings of the edges of G with k given colors is at least (\frac{(k!)^2}{k^k})^n.

—————————————————————————-

7. The Strong Perfect Graph Conjecture (resolved)

Theorem : A graph is perfect if and only if it does not contain, as an induced subgraph, an odd hole or an odd antihole.

—————————————————————————-

by

Book Review of “Elements of Automata Theory”

During summer 2010 I started reading a book titled Elements of Automata Theory by Jacques Sakarovitch. It took me one year to read the book and submit my review to Bill Gasarch during summer 2011. It will be appearing in SIGACT book review column soon. I am posting my review here for the benefit of everybody.


———————————————————————————————————————————

Book : Elements of Automata Theory by Jacques Sakarovitch
Reviewer : Shiva Kintali

Introduction

During my undergrad I often found myself captivated by the beauty and depth of automata theory. I wanted to read one book on automata theory and say that I “know” automata theory. Couple of years later I realized that it is silly to expect such a book. The depth and breadth of automata theory cannot be covered by a single book.

My PhD thesis is heavily inspired by automata theory. I had to read several (fifty year old) papers and books related to automata theory to understand several fundamental theorems. Unfortunately, the concepts I wanted to learn are scattered in multiple books and old research papers, most of which are hard to find. When I noticed that Prof. Bill Gasarch is looking for a review of Elements of Automata Theory, I was very excited and volunteered to review it, mainly because I wanted to increase my knowledge about automata theory. Given my background in parsing technologies and research interests in space-bounded computation I wanted to read this book carefully. This book is around 750 pages long and it took me around one year to (approximately) read it. It is very close to my expectations of the one book on automata theory.

First impressions : Most of the books on automata theory start with the properties of regular languages, finite automata, pushdown automata, context-free languages, pumping lemmas, Chomsky hierarchy, decidability and conclude with NP-completeness and the P vs NP problem. This book is about “elements” of automata theory. It focuses only on finite automata over different mathematical structures. It studies pushdown automata only in the context of rational subsets in the free group. Yes, there is 750 pages worth literature studying only finite automata.

This book is aimed at people enthusiastic to know the subject rigorously and not intended as a textbook for automata theory course. It can also be used by advanced researchers as a desk reference. There is no prerequisite to follow this book, except for a reasonable mathematical maturity. It can be used as a self-study text. This book is a direct translation of its french original.

 
Summary

This book is divided into five major chapters. The first three chapters deal with the notions of rationality and recognizability. A family of languages are rationally closed if it is closed under rational operations (union, product and star). A language is reconizable if there exists a finite automata that recognizes it. The fourth and fifth chapters discuss rationality in relations. Chapter 0 acts as an appendix of several definitions of structures such as relations, monoids, semirings, matrices, graphs and concepts such as decidability. Following is a short summary of the five major chapters. There are several deep theorems (for example, Higman’s Theorem) studied in this book. I cannot list all of them here. The chapter summaries in the book have more details.

Chapter 1 essentially deals with the basic definitions and theorems required for any study of automata theory. It starts with the definitions of states, transitions, (deterministic and nondeterministic) automaton, transpose, ambiguity and basic operations such as union, cartesian product, star, quotient of a language. Rational operators, rational languages and rational expressions are defined and the relation between rationality and recognizability is established leading to the proof of Kleene’s theorem. String matching (i.e., finding a word in a text) is studied in detail as an illustrative example. Several theorems related to star height of languages are proved. A fundamental theorem stating that `the language accepted by a two-way automaton is rational’ is proved. The distinction between Moore and Mealy machines is introduced.

Chapter 2 deals with automata over the elements of an arbitrary monoid and the distinction between rational set and recognizable set in this context. This leads to a better understanding of Kleene’s theorem. The notion of morphism of automata is introduced and several properties of morphisms and factorisations are presented. Conway’s construction of universally minimal automaton is explained and the importance of well quasi-orderings is explained in detail. Based on these established concepts, McNaughton’s theorem (which states that the star height of a rational group language is computable) is studied with a new perspective.

Chapter 3 formalizes the notion of “weighted” automata that count the number of computations that make an element be accepted by an automaton, thus generalizing the previously introduced concepts in a new dimension. Languages are generalized to formal series and actions are generalized to representations. The concepts and theorems in this chapter makes the reader appreciate the deep connections of automata theory with several branches of mathematics. I personally enjoyed reading this chapter more than any other chapter in this book.

Chapter 4 builds an understanding of the relations realized by different finite automata in the order they are presented in chapters 1, 2 and 3. The Evaluation Theorem and the Composition Theorem play a central role in understanding this study. The decidability of the equivalence of transducers (with and without weigths) is studied. This chapter concludes with the study of deterministic and synchronous relations.

Chapter 5 studies the functions realized by finite automata. Deciding functionality, sequential functions, uniformisation of rational relations by rational functions, semi-monomial matrix representation, translations of a function and uniformly bounded functions are studied.

There are exercises (with solutions) at the end of every section of every chapter. These exercises are very carefully designed and aid towards better understanding of the corresponding concepts. First time readers are highly encouraged to solve (or at least glance through) these exercises. Every section ends with Notes and References mentioning the corresponding references and a brief historical summary of the chapter.

 
Opinion

Overall I found the book very enlightening. It has provided me new perspectives on several theorems that I assumed I understood completely. Most of the concepts in this book are new to me and I had no problems following the concepts and the corresponding theorems. The related exercises made these topics even more fun to learn. It was a joy for me to read this book and I recommend this book for anyone who is interested in automata theory (or more generally complexity theory) and wants to know the fundamental theorems of theory of computing. If you are a complexity theorist, it is worthwhile to look back at the foundations of theory of computing to better appreciate its beauty and history. This book is definitely unique in its approach and the topics chosen. Most of the topics covered are either available in very old papers or not accesible at all. I applaud the author for compiling these topics into a wonderful free-flowing text.

This book is nicely balanced between discussions of concepts and formal proofs. The writing is clear and the topics are organized very well from the most specific to the most general, making it a free-flowing text. On the other hand, it is very dense and requires lots of motivation and patience to read and understand the theorems. The author chose a rigorous way of explaining rationality and recognizability. Sometimes you might end up spending couple of hours to read just two pages. Such is the depth of the topics covered. Beginners might find this book too much to handle. I encourage beginners to read this book after taking an introductory automata theory course. This is definitely a very good reference text for researchers in the field of automata theory.

In terms of being used in a course, I can say that a graduate level course can be designed from a carefully chosen subset of the topics covered in this book. The exercises in the book can be readily used for such a course.

This is an expensive book, which is understandable based on the author’s efforts to cover several fundamental topics (along with exercises) in such a depth. If you think it is expensive, I would definitely suggest that you get one for your library.

———————————————————————————————————————————

by

FOCS 2012 Accepted Papers (with pdf files)

FOCS 2012 accepted paper list is here. Following are PDF pointers to online versions.

Tight Bounds for Randomized Load Balancing on Arbitrary Network Topologies [arXiv]
Thomas Sauerwald and He Sun 

Population Recovery and Partial Identification [pdf]
Avi Wigderson and Amir Yehudayoff 

A direct product theorem for the two-party bounded-round public-coin communication 
complexity [pdf]
Rahul Jain and Attila Pereszlenyi and Penghui Yao 

Positive Results for Concurrently Secure Computation in the Plain Model [pdf]
Vipul Goyal 

Constructive Discrepancy Minimization by Walking on The Edges [arXiv]
Shachar Lovett and Raghu Meka 

Making the Long Code Shorter [pdf]
Boaz Barak and Parikshit Gopalan and Johan Hastad and Raghu Meka and Prasad 
Raghavendra and David Steurer 

On the homotopy test on surfaces [arXiv]
Francis Lazarus and Julien Rivaud 

Constructing a Pseudorandom Generator Requires an Almost Linear Number of Calls [arXiv]
Thomas Holenstein and Makrand Sinha 

Partially Symmetric Functions are Efficiently Isomorphism-Testable [arXiv]
Eric Blais and Amit Weinstein and Yuichi Yoshida 

The computational hardness of counting in two-spin models on d-regular graphs [arXiv]
Allan Sly and Nike Sun 

A PTAS for Computing the Supremum of Gaussian Processes	[arXiv]
Raghu Meka 

The tile assembly model is intrinsically universal [arXiv]
David Doty and Jack H. Lutz and Matthew J. Patitz and Robert T. Schweller and 
Scott M. Summers and Damien Woods 

Hardness of Finding Independent Sets in Almost q-Colorable Graphs
Subhash Khot and Rishi Saket 

The Privacy of the Analyst and The Power of the State
Cynthia Dwork and Moni Naor and Salil Vadhan 

Higher Cell Probe Lower Bounds for Evaluating Polynomials
Kasper Green Larsen 

Faster Algorithms for Rectangular Matrix Multiplication	[arXiv]
Francois Le Gall 

A Polylogarithimic Approximation Algorithm for Edge-Disjoint Paths 
with Congestion 2
Julia Chuzhoy and Shi Li 

Iterative rounding approximation algorithms for degree-bounded node-connectivity 
network design	[arXiv]
Takuro Fukunaga and R. Ravi 

Pseudorandomness from Shrinkage	[ECCC]
Russell Impagliazzo and Raghu Meka and David Zuckerman 

An additive combinatorics approach relating rank to communication complexity [ECCC]
Eli Ben-Sasson and Shachar Lovett and Noga Ron-Zewi 

Designing FPT algorithms for cut problems using randomized contractions	
Rajesh Chitnis and Marek Cygan and MohammadTaghi Hajiaghayi and Marcin Pilipczuk and 
Micha� Pilipczuk 

Sparse affine-invariant linear codes are locally testable [ECCC]
Eli Ben-Sasson and Noga Ron-Zewi and Madhu Sudan 

A Structure Theorem for Poorly Anticoncentrated Gaussian Chaoses and Applications 
to the Study of Polynomial Threshold Functions [arXiv]
Daniel M. Kane 

How to Construct Quantum Random Functions [ePrint]
Mark Zhandry 

A weight-scaling algorithm for min-cost imperfect matchings in bipartite graphs	[pdf]
Lyle Ramshaw and Robert E. Tarjan 

Matching with our Eyes Closed	
Gagan Goel and Pushkar Tripathi 

A New Infinity of Distance Oracles for Sparse Graphs
Mihai Patrascu and Liam Roditty and Mikkel Thorup 

A Permanent Approach to the Traveling Salesman Problem
Nisheeth K. Vishnoi 

Everywhere-Sparse Spanners via Dense Subgraphs [arXiv]
Eden Chlamtac and Michael Dinitz and Robert Krauthgamer 

Learning-graph-based Quantum Algorithm for k-distinctness [arXiv]
Aleksandrs Belovs 

Beck's three permutations conjecture: A counterexample and some consequences
Alantha Newman and Ofer Neiman and Aleksandar Nikolov 

Down the Rabbit Hole: Robust Proximity Search and Density Estimation in 
Sublinear Space	[pdf]
Sariel Har-Peled and Nirman Kumar 

On the complexity of finding narrow proofs [arXiv]
Christoph Berkholz 

Improved Distance Sensitivity Oracles via Fast Single-Source Replacement Paths
Fabrizio Grandoni and Virginia Vassilevska Williams 

LP Rounding for k-Centers with Non-uniform Hard Capacities
Marek Cygan and MohammadTaghi Hajiaghayi and Samir Khuller 

A Tight Combinatorial Algorithm for Submodular Maximization Subject to a 
Matroid Constraint [arXiv]
Yuval Filmus and Justin Ward 

Faster SDP hierarchy solvers for local rounding algorithms
Venkatesan Guruswami and Ali Kemal Sinop 

Combinatorial coloring of 3-colorable graphs [arXiv]
Ken-ichi Kawarabayashi and Mikkel Thorup 

Approximation Limits of Linear Programs (Beyond Hierarchies) [arXiv]
Gábor Braun and Samuel Fiorini and Sebastian Pokutta and David Steurer 

A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular 
Maximization
Niv Buchbinder and Moran Feldman and Joseph (Seffi) Naor and Roy Schwartz 

Lower bounds on Information Complexity via zero-communication protocols 
and applications [arXiv]
Iordanis Kerenidis and Sophie Laplante and Virginie Lerays and Jeremie Roland 
and David Xiao 

Better Pseudorandom Generators from Milder Pseudorandom Restrictions
Parikshit Gopalan and Raghu Meka and Omer Reingold and Luca Trevisan and Salil Vadhan 

Almost Optimal Canonical Property Testers for Satisfiability
Christian Sohler 

On Range Searching with Semialgebraic Sets II
Pankaj K. Agarwal and Jiri Matousek and Micha Sharir 

MIP* contains NEXP
Tsuyoshi Ito and Thomas Vidick 

Geometric Complexity Theory V: Equivalence between blackbox derandomization 
of polynomial identity testing and derandomization of Noether's normalization lemma
Ketan D. Mulmuley 

Single Source - All Sinks Max Flows in Planar Digraphs 
Jakub Lacki and Yahav Nussbaum and Piotr Sankowski and Christian Wulff-Nilsen 

The Johnson-Lindenstrauss Transform Itself Preserves Differential Privacy [arXiv] 
Jeremiah Blocki and Avrim Blum and Anupam Datta and Or Sheffet 

Formulas Resilient to Short-Circuit Errors
Yael Kalai and Allison Lewko and Anup Rao 

Efficient Interactive Coding Against Adversarial Noise [ECCC]
Zvika Brakerski and Yael Tauman Kalai 

How to Allocate Tasks Asynchronously
Dan Alistarh and Michael A. Bender and Seth Gilbert and Rachid Guerraoui 

New Limits to Classical and Quantum Instance Compression [pdf]
Andrew Drucker 

Large Deviation Bounds for Decision Trees and Sampling Lower Bounds 
for AC0-circuits [ECCC]
Chris Beck and Russell Impagliazzo and Shachar Lovett 

The Locality of Distributed Symmetry Breaking [arXiv]
Leonid Barenboim and Michael Elkin and Seth Pettie and Johannes Schneider 

Representative sets and irrelevant vertices: New tools for kernelization [arXiv]
Stefan Kratsch and Magnus Wahlström 

Approximating the Expansion Profile and Almost Optimal Local 
Graph Clustering [arXiv]
Shayan Oveis Gharan and Luca Trevisan 

Algorithmic Applications of Baur-Strassen's Theorem: Shortest Cycles, 
Diameter and Matchings [arXiv]
Marek Cygan and Harold N. Gabow and Piotr Sankowski 

Learning Topic Models --- Going beyond SVD [arXiv]	  
Sanjeev Arora and Rong Ge and Ankur Moitra 

Non-Malleable Extractors, Two-Source Extractors and Privacy Amplification
Xin Li 

The power of linear programming for valued CSPs	[arXiv]
Johan Thapper and Stanislav Zivny 

Constructing Non-Malleable Commitments: A Black-Box Approach
Vipul Goyal and Chen-Kuei Lee and Rafail Ostrovsky and Ivan Visconti 

Active Property Testing [pdf]
Maria-Florina Balcan and Eric Blais and Avrim Blum and Liu Yang 

The Dynamics of Influence Systems [arXiv]
Bernard Chazelle 

Online Matching with Stochastic Rewards	
Aranyak Mehta and Debmalya Panigrahi 

Finding Correlations in Subquadratic Time, with Applications to 
Learning Parities and Juntas [ECCC]
Gregory Valiant 

The Exponential Mechanism for Social Welfare: Private, Truthful, 
and Nearly Optimal [arXiv]
Zhiyi Huang and Sampath Kannan 

How to Compute in the Presence of Leakage [ECCC]
Shafi Goldwasser and Guy Rothblum 

On-line Indexing for General Alphabets
Tsvi Kopelowitz 

Optimal Multi-Dimensional Mechanism Design: Reducing Revenue to 
Welfare Maximization
Yang Cai and Constantinos Daskalakis and S. Matthew Weinberg 

Split and Join: Strong Partitions and Universal Steiner Trees for Graphs [arXiv]
Costas Busch and Chinmoy Dutta and Jaikumar Radhakrishnan and 
Rajmohan Rajaraman and Srivathsan Srinivasagopalan 

From the Impossibility of Obfuscation to a New Non-Black-Box 
Simulation Technique  
Nir Bitansky and Omer Paneth 

Quasi-optimal multiplication of linear differential operators
Alexandre Benoit and Alin Bostan and Joris van der Hoeven 

Randomized Greedy Algorithms for the Maximum Matching Problem 
with New Analysis	
Matthias Poloczek and Mario Szegedy 

Concave Generalized Flows with Applications to Market Equilibria [arXiv]
Laszlo A. Vegh 

The Cutting Plane Method is Polynomial for Perfect Matchings
Karthekeyan Chandrasekaran and Laszlo A. Vegh and Santosh S. Vempala 

Computing Multiplicities of Lie Group Representations [arXiv]
Matthias Christandl and Brent Doran and Michael Walter 

A New Direction for Counting Perfect Matchings
Taisuke Izumi and Tadashi Wadayama 

Planar F-Deletion: Approximation, Kernelization and Optimal FPT Algorithms [pdf]
Fedor Fomin and Daniel Lokshtanov and Neeldhara Misra and Saket Saurabh 

Lower Bounds for Interactive Compression by Constant-Depth Circuits
Arkadev Chattopadhyay and Rahul Santhanam
by

TrueShelf

I have been teaching (courses related to algorithms and complexity) for the past six years (five years as a PhD student at GeorgiaTech, and the past one year at Princeton). One of the most challenging and interesting part of teaching is creating new exercises to help teach the important concepts in an efficient way. We often need lots of problems to include in homeworks, midterms, final exams and also to create practice problem sets.

We do not get enough time to teach all the concepts in class because the number of hours/week is bounded. I personally like to teach only the main concepts in class and design good problem sets so that students can learn the generalizations or extensions of the concepts by solving problems hands-on. This helps them develop their own intuitions about the concepts.

Whenever I need a new exercise I hardly open a physical textbook. I usually search on internet and find exercises from a course website (or) “extract” an exercise from a research paper. There are hundreds of exercises “hidden” in pdf files across several course homepages. Instructors often spend lots of time designing them. If these exercises can reach all the instructors and students across the world in an efficiently-indexed form, that will help everybody. Instructors will be happy that the exercises they designed are not confined to just one course. Students will have an excellent supply of exercises to hone their problem-solving skills.

During 2008, half-way through my PhD, I started collected the exercises I like in a private blog. At the same time I registered the domain trueshelf.com to make these exercises public. In 2011, towards the end of my PhD, I started using the trueshelf.com domain and made a public blog so that anybody can post an exercise. [ Notice that I did not use the trueshelf.com domain for three years. During these three years I got several offers ranging upto $5000 to sell the domain. So I knew I got the right name :) ] Soon, I realized that wordpress is somewhat “static” in nature and does not have enough “social” features I wanted. A screenshot of the old website is shown below.

The new version of TrueShelf is a social website enabling “crowd-sourcing” of exercises in any area. Here is the new logo, I am excited about :)

The goal of TrueShelf is to aid both the instructors and students by presenting quality exercises with tag-based indexing. Read the TrueShelf FAQ for more details. Note that we DO NOT allow users to post solutions. Each user may add his own “private” solution and notes to any exercise. I am planning to add more features soon.

In the long-run, I see TrueShelf becoming a ”Youtube for exercises”. Users will be able to create their own playlists of exercises (a.k.a problem sets) and will be recommended relevant exercises. Test-preparation agencies will be able to create their own channels to create sample tests.

Feel free to explore TrueShelf, contribute new exercises and let me know if you have any feedback (or) new features you want to see. You can also follow TrueShelf on facebook, twitter and google+.

Let’s see how TrueShelf evolves.

by

Turing Centennial Celebration – Day 3

Welcome to Day 3 proceedings of Turing Centennial Celebration. See also Day 1 and Day 2.

  • David Harel’s talk titled “Standing on the Shoulders of a Giant”

  • An entertaining musical video about Turing test

  • Avi Wigderson’s tak titled “The Hardness of Proving Computational Hardness”. It is always exciting to watch Avi’s talks.

  • Avi says “Easiness and Hardness are two sides of the same Mobius strip”.

  • Shafi Goldwasser’s talk titled “Pseudo Deterministic Algorithms”

  • Bob Tarjan’s talk titled “Search Tree Mysteries”.

  • Dick Lipton’s talk titled “What Would Turing Be Doing Today?”. As usual Dick’s talk is very entertaining. So I took more pictures.

  • “Making Projectors work” is a grand challenge :)

  • Birds vs Frogs
  • End of Dick’s talk

  • Christos Papadimitriou’s talk titled “The Origin of Computable Numbers”. Amazing talk comparing Turing and Darwin.

 

The three day Turing Centennial celebration comes to an end :(

 

by

Turing Centennial Celebration – Day 2

Welcome to Day 2 proceedings of Turing Centennial Celebration. Click here for yesterday’s events. Thanks to a comment of Noman, live VIDEO is also  available.

  • Martin Davis talks about “Universality is Ubiquitous”. The following slide is from Turing’s 1947 Lecture to the London Mathematical Society.

  • James Murray starts his talk titled “Mathematical Biology, Past, Present and Future: from animal coat patterns to brain tumors to saving marriages”

  • Now I understand “How the leopard gets its spots ?”

  • Barbara Liskov’s talk titled “Programming the Turing Machine”.

  • Tom Mitchell’s talk titled “Never-Ending Language Learning”. The following slide has a quote of Alan Turing, “What we want is a machine that can learn from experience”.

  • Andrew Odlyzko’s talk titled “Turing and the Riemann zeta function”.

  • Ron Rivest’s talk titled “The Growth of Cryptography”

  • Getting ready for dinner

  • Books about Alan Turing

  • Andrew Appel talking about “Turing, Gödel, and Church at Princeton in the 1930s”. This is an inspiring talk about the history of the origins of computing and programming languages at Princeton in 1930s.

  • Jack Emery, producer of the movie talking about his inspiration behind making “Breaking the Code“

  • I expected this movie to be a slow documentary. But it exceeded all my expectations. It has sharp dialogues, slick editing and top-notch performances.
  • Here is a sample of a mathematical conversation

 

  • Here is another sample
  • That’s all for today. Tune in tomorrow for Day 3 proceedings.